LevenshteinTransformation.php

Go to the documentation of this file.

<?php

declare(strict_types=1);

namespace ILIAS\Refinery\String\Transformation;

use ILIAS\Refinery\DeriveApplyToFromTransform;
use ILIAS\Refinery\DeriveInvokeFromTransform;
use ILIAS\Refinery\Transformation;
use InvalidArgumentException;
use ilStr;

class LevenshteinTransformation implements Transformation
{
    use DeriveApplyToFromTransform;
    use DeriveInvokeFromTransform;

    private string $primary_string;
    private int $maximum_distance;
    private float $cost_insertion;
    private float $cost_replacement;
    private float $cost_deletion;

    public function __construct(
        string $primary_string = '',
        int $maximum_distance = 0,
        float $cost_insertion = 1.0,
        float $cost_replacement = 1.0,
        float $cost_deletion = 1.0
    ) {
        $this->primary_string = $primary_string;
        $this->maximum_distance = $maximum_distance;
        $this->cost_insertion = $cost_insertion;
        $this->cost_replacement = $cost_replacement;
        $this->cost_deletion = $cost_deletion;
    }

    protected function levenshtein(string $secondary_string): float
    {
        $cost_matrix = [];
        $primary_string_array = $this->stringToCharacterArray($this->primary_string);
        $secondary_string_array = $this->stringToCharacterArray($secondary_string);
        $primary_string_length = count($primary_string_array);
        $secondary_string_length = count($secondary_string_array);

        // if the difference between string length is bigger than the maximum allowed levenshtein distance
        // the code can be skipped
        if ($this->maximum_distance !== 0 && abs($primary_string_length - $secondary_string_length) > $this->maximum_distance) {
            return -1.0;
        }

        $current_row = [];
        $current_row[0] = 0.0;
        for ($j = 1; $j < $secondary_string_length + 1; $j++) {
            $current_row[$j] = $j * $this->cost_insertion;
        }

        $cost_matrix[0] = $current_row;
        for ($i = 0; $i < $primary_string_length; $i++) {
            $current_row = [];
            $current_row[0] = ($i + 1) * $this->cost_deletion;
            for ($j = 0; $j < $secondary_string_length; $j++) {
                $current_row[$j + 1] = min(
                    $cost_matrix[$i][$j + 1] + $this->cost_deletion,
                    $current_row[$j] + $this->cost_insertion,
                    $cost_matrix[$i][$j] + ($primary_string_array[$i] === $secondary_string_array[$j] ? 0.0 : $this->cost_replacement)
                );
            }
            // maximum distance reached
            if ($this->maximum_distance !== 0 && min($current_row) > $this->maximum_distance) {
                return -1.0;
            }
            $cost_matrix[$i + 1] = $current_row;
        }
        if ($cost_matrix[$primary_string_length][$secondary_string_length] > $this->maximum_distance && $this->maximum_distance != 0) {
            return -1.0;
        }
        return $cost_matrix[$primary_string_length][$secondary_string_length];
    }

    private function stringToCharacterArray(string $string_to_convert): array
    {
        $length = ilStr::strLen($string_to_convert);
        $character_array = [];
        for ($index = 0; $index < $length; $index++) {
            $character_array[$index] = ilStr::subStr($string_to_convert, $index, 1);
        }
        return $character_array;
    }

    public function transform($from): float
    {
        if (!is_string($from)) {
            throw new InvalidArgumentException(__METHOD__ . " the argument is not a string.");
        }

        return $this->levenshtein($from);
    }
}