Oefenweb / damerau-levenshtein

tests/DamerauLevenshteinTest.php

Indentation +317 added lines, -317 removed lines

@@ -6,321 +6,321 @@
 class DamerauLevenshteinTest extends \PHPUnit_Framework_TestCase
 {
 
-    /**
-     * Tests `getSimilarity`.
-     *
-     * @return void
-     */
-    public function testGetSimilarity()
-    {
-        $inputs = [
-            ['foo', 'foo'],
-            ['foo', 'fooo'],
-            ['foo', 'bar'],
-
-            ['123', '12'],
-            ['qwe', 'qwa'],
-            ['awe', 'qwe'],
-            ['фыв', 'фыа'],
-            ['vvvqw', 'vvvwq'],
-            ['qw', 'wq'],
-            ['qq', 'ww'],
-            ['qw', 'qw'],
-            ['пионер', 'плеер'],
-            ['пионер', 'пионеер'],
-            ['пионер', 'поинер'],
-            ['pioner', 'poner'],
-            ['пионер', 'понер'],
-        ];
-        $outputs = [
-            0,
-            1,
-            3,
-
-            1,
-            1,
-            1,
-            1,
-            1,
-            1,
-            2,
-            0,
-            3,
-            1,
-            1,
-            1,
-            1,
-        ];
-
-        foreach ($inputs as $i => $input) {
-            $DamerauLevenshtein = new DamerauLevenshtein($input[0], $input[1]);
-            $result = $DamerauLevenshtein->getSimilarity();
-            $expected = $outputs[$i];
-
-            $this->assertSame($expected, $result);
-        }
-    }
-
-    /**
-     * Tests `getInsCost`.
-     *
-     * @return void
-     */
-    public function testGetInsCost()
-    {
-        list($firstString, $secondString) = $this->getDefaultStrings();
-        list($insCost, $delCost, $subCost, $transCost) = $this->getDefaultCosts();
-
-        // Default insert cost
-
-        $DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
-        $result = $DamerauLevenshtein->getInsCost();
-        $expected = $insCost;
-
-        $this->assertSame($expected, $result);
-
-        // Non-default insert cost
-
-        $insCost = 2;
-
-        $DamerauLevenshtein = new DamerauLevenshtein(
-            $firstString,
-            $secondString,
-            $insCost,
-            $delCost,
-            $subCost,
-            $transCost
-        );
-        $result = $DamerauLevenshtein->getInsCost();
-        $expected = $insCost;
-
-        $this->assertSame($expected, $result);
-    }
-
-    /**
-     * Tests `getDelCost`.
-     *
-     * @return void
-     */
-    public function testGetDelCost()
-    {
-        list($firstString, $secondString) = $this->getDefaultStrings();
-        list($insCost, $delCost, $subCost, $transCost) = $this->getDefaultCosts();
-
-        // Default delete cost
-
-        $DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
-        $result = $DamerauLevenshtein->getDelCost();
-        $expected = $delCost;
-
-        $this->assertSame($expected, $result);
-
-        // Non-default delete cost
-
-        $delCost = 2;
-
-        $DamerauLevenshtein = new DamerauLevenshtein(
-            $firstString,
-            $secondString,
-            $insCost,
-            $delCost,
-            $subCost,
-            $transCost
-        );
-        $result = $DamerauLevenshtein->getDelCost();
-        $expected = $delCost;
-
-        $this->assertSame($expected, $result);
-    }
-
-    /**
-     * Tests `getSubCost`.
-     *
-     * @return void
-     */
-    public function testGetSubCost()
-    {
-        list($firstString, $secondString) = $this->getDefaultStrings();
-        list($insCost, $delCost, $subCost, $transCost) = $this->getDefaultCosts();
-
-        // Default substitution cost
-
-        $DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
-        $result = $DamerauLevenshtein->getSubCost();
-        $expected = $subCost;
-
-        $this->assertSame($expected, $result);
-
-        // Non-default substitution cost
-
-        $subCost = 2;
-
-        $DamerauLevenshtein = new DamerauLevenshtein(
-            $firstString,
-            $secondString,
-            $insCost,
-            $delCost,
-            $subCost,
-            $transCost
-        );
-        $result = $DamerauLevenshtein->getSubCost();
-        $expected = $subCost;
-
-        $this->assertSame($expected, $result);
-    }
-
-    /**
-     * Tests `getTransCost`.
-     *
-     * @return void
-     */
-    public function testGetTransCost()
-    {
-        list($firstString, $secondString) = $this->getDefaultStrings();
-        list($insCost, $delCost, $subCost, $transCost) = $this->getDefaultCosts();
-
-        // Default transposition cost
-
-        $DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
-        $result = $DamerauLevenshtein->getTransCost();
-        $expected = $transCost;
-
-        $this->assertSame($expected, $result);
-
-        // Non-default transposition cost
-
-        $transCost = 2;
-
-        $DamerauLevenshtein = new DamerauLevenshtein(
-            $firstString,
-            $secondString,
-            $insCost,
-            $delCost,
-            $subCost,
-            $transCost
-        );
-        $result = $DamerauLevenshtein->getTransCost();
-        $expected = $transCost;
-
-        $this->assertSame($expected, $result);
-    }
-
-    /**
-     * Tests `getRelativeDistance`.
-     *
-     * @return void
-     */
-    public function testGetRelativeDistance()
-    {
-        $delta = pow(10, -4);
-
-        $firstString = 'O\'Callaghan';
-        $secondString = 'OCallaghan';
-
-        $DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
-        $result = $DamerauLevenshtein->getRelativeDistance();
-        $expected = 0.90909090909091;
-        $this->assertEquals($expected, $result, '', $delta);
-
-        $firstString = 'Thom';
-        $secondString = 'Mira';
-
-        $DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
-        $result = $DamerauLevenshtein->getRelativeDistance();
-        $expected = 0.0;
-        $this->assertEquals($expected, $result, '', $delta);
-
-        $firstString = 'Oldeboom';
-        $secondString = 'Ven';
-
-        $DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
-        $result = $DamerauLevenshtein->getRelativeDistance();
-        $expected = 0.125;
-        $this->assertEquals($expected, $result, '', $delta);
-
-        $firstString = 'ven';
-        $secondString = 'Ven';
-
-        $DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
-        $result = $DamerauLevenshtein->getRelativeDistance();
-        $expected = 0.66666666666667;
-        $this->assertEquals($expected, $result, '', $delta);
-
-        $firstString = 'enV';
-        $secondString = 'Ven';
-
-        $DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
-        $result = $DamerauLevenshtein->getRelativeDistance();
-        $expected = 0.33333333333333;
-        $this->assertEquals($expected, $result, '', $delta);
-    }
-
-    /**
-     * Tests `getMatrix`.
-     *
-     * @return void
-     */
-    public function testGetMatrix()
-    {
-        list($firstString, $secondString) = $this->getDefaultStrings();
-
-        $DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
-        $actual = $DamerauLevenshtein->getMatrix();
-        $expected = [
-            [0, 1, 2, 3],
-            [1, 1, 2, 3],
-            [2, 2, 2, 3],
-            [3, 3, 3, 3]
-        ];
-        $this->assertSame($expected, $actual);
-    }
-
-    /**
-     * Tests `displayMatrix`.
-     *
-     * @return void
-     */
-    public function testDisplayMatrix()
-    {
-        list($firstString, $secondString) = $this->getDefaultStrings();
-
-        $DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
-        $actual = $DamerauLevenshtein->displayMatrix();
-        $expected = implode('', [
-            "  foo\n",
-            " 0123\n",
-            "b1123\n",
-            "a2223\n",
-            "r3333\n",
-        ]);
-        $this->assertSame($expected, $actual);
-    }
-
-    /**
-     * Returns the default costs.
-     *
-     * @return array Costs (insert, delete, substitution, transposition)
-     */
-    protected function getDefaultCosts()
-    {
-        $insCost = 1;
-        $delCost = 1;
-        $subCost = 1;
-        $transCost = 1;
-
-        return [$insCost, $delCost, $subCost, $transCost];
-    }
-
-    /**
-     * Returns the default strings.
-     *
-     * @return array Strings (foo, bar)
-     */
-    protected function getDefaultStrings()
-    {
-        $firstString = 'foo';
-        $secondString = 'bar';
-
-        return [$firstString, $secondString];
-    }
+	/**
+	 * Tests `getSimilarity`.
+	 *
+	 * @return void
+	 */
+	public function testGetSimilarity()
+	{
+		$inputs = [
+			['foo', 'foo'],
+			['foo', 'fooo'],
+			['foo', 'bar'],
+
+			['123', '12'],
+			['qwe', 'qwa'],
+			['awe', 'qwe'],
+			['фыв', 'фыа'],
+			['vvvqw', 'vvvwq'],
+			['qw', 'wq'],
+			['qq', 'ww'],
+			['qw', 'qw'],
+			['пионер', 'плеер'],
+			['пионер', 'пионеер'],
+			['пионер', 'поинер'],
+			['pioner', 'poner'],
+			['пионер', 'понер'],
+		];
+		$outputs = [
+			0,
+			1,
+			3,
+
+			1,
+			1,
+			1,
+			1,
+			1,
+			1,
+			2,
+			0,
+			3,
+			1,
+			1,
+			1,
+			1,
+		];
+
+		foreach ($inputs as $i => $input) {
+			$DamerauLevenshtein = new DamerauLevenshtein($input[0], $input[1]);
+			$result = $DamerauLevenshtein->getSimilarity();
+			$expected = $outputs[$i];
+
+			$this->assertSame($expected, $result);
+		}
+	}
+
+	/**
+	 * Tests `getInsCost`.
+	 *
+	 * @return void
+	 */
+	public function testGetInsCost()
+	{
+		list($firstString, $secondString) = $this->getDefaultStrings();
+		list($insCost, $delCost, $subCost, $transCost) = $this->getDefaultCosts();
+
+		// Default insert cost
+
+		$DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
+		$result = $DamerauLevenshtein->getInsCost();
+		$expected = $insCost;
+
+		$this->assertSame($expected, $result);
+
+		// Non-default insert cost
+
+		$insCost = 2;
+
+		$DamerauLevenshtein = new DamerauLevenshtein(
+			$firstString,
+			$secondString,
+			$insCost,
+			$delCost,
+			$subCost,
+			$transCost
+		);
+		$result = $DamerauLevenshtein->getInsCost();
+		$expected = $insCost;
+
+		$this->assertSame($expected, $result);
+	}
+
+	/**
+	 * Tests `getDelCost`.
+	 *
+	 * @return void
+	 */
+	public function testGetDelCost()
+	{
+		list($firstString, $secondString) = $this->getDefaultStrings();
+		list($insCost, $delCost, $subCost, $transCost) = $this->getDefaultCosts();
+
+		// Default delete cost
+
+		$DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
+		$result = $DamerauLevenshtein->getDelCost();
+		$expected = $delCost;
+
+		$this->assertSame($expected, $result);
+
+		// Non-default delete cost
+
+		$delCost = 2;
+
+		$DamerauLevenshtein = new DamerauLevenshtein(
+			$firstString,
+			$secondString,
+			$insCost,
+			$delCost,
+			$subCost,
+			$transCost
+		);
+		$result = $DamerauLevenshtein->getDelCost();
+		$expected = $delCost;
+
+		$this->assertSame($expected, $result);
+	}
+
+	/**
+	 * Tests `getSubCost`.
+	 *
+	 * @return void
+	 */
+	public function testGetSubCost()
+	{
+		list($firstString, $secondString) = $this->getDefaultStrings();
+		list($insCost, $delCost, $subCost, $transCost) = $this->getDefaultCosts();
+
+		// Default substitution cost
+
+		$DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
+		$result = $DamerauLevenshtein->getSubCost();
+		$expected = $subCost;
+
+		$this->assertSame($expected, $result);
+
+		// Non-default substitution cost
+
+		$subCost = 2;
+
+		$DamerauLevenshtein = new DamerauLevenshtein(
+			$firstString,
+			$secondString,
+			$insCost,
+			$delCost,
+			$subCost,
+			$transCost
+		);
+		$result = $DamerauLevenshtein->getSubCost();
+		$expected = $subCost;
+
+		$this->assertSame($expected, $result);
+	}
+
+	/**
+	 * Tests `getTransCost`.
+	 *
+	 * @return void
+	 */
+	public function testGetTransCost()
+	{
+		list($firstString, $secondString) = $this->getDefaultStrings();
+		list($insCost, $delCost, $subCost, $transCost) = $this->getDefaultCosts();
+
+		// Default transposition cost
+
+		$DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
+		$result = $DamerauLevenshtein->getTransCost();
+		$expected = $transCost;
+
+		$this->assertSame($expected, $result);
+
+		// Non-default transposition cost
+
+		$transCost = 2;
+
+		$DamerauLevenshtein = new DamerauLevenshtein(
+			$firstString,
+			$secondString,
+			$insCost,
+			$delCost,
+			$subCost,
+			$transCost
+		);
+		$result = $DamerauLevenshtein->getTransCost();
+		$expected = $transCost;
+
+		$this->assertSame($expected, $result);
+	}
+
+	/**
+	 * Tests `getRelativeDistance`.
+	 *
+	 * @return void
+	 */
+	public function testGetRelativeDistance()
+	{
+		$delta = pow(10, -4);
+
+		$firstString = 'O\'Callaghan';
+		$secondString = 'OCallaghan';
+
+		$DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
+		$result = $DamerauLevenshtein->getRelativeDistance();
+		$expected = 0.90909090909091;
+		$this->assertEquals($expected, $result, '', $delta);
+
+		$firstString = 'Thom';
+		$secondString = 'Mira';
+
+		$DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
+		$result = $DamerauLevenshtein->getRelativeDistance();
+		$expected = 0.0;
+		$this->assertEquals($expected, $result, '', $delta);
+
+		$firstString = 'Oldeboom';
+		$secondString = 'Ven';
+
+		$DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
+		$result = $DamerauLevenshtein->getRelativeDistance();
+		$expected = 0.125;
+		$this->assertEquals($expected, $result, '', $delta);
+
+		$firstString = 'ven';
+		$secondString = 'Ven';
+
+		$DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
+		$result = $DamerauLevenshtein->getRelativeDistance();
+		$expected = 0.66666666666667;
+		$this->assertEquals($expected, $result, '', $delta);
+
+		$firstString = 'enV';
+		$secondString = 'Ven';
+
+		$DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
+		$result = $DamerauLevenshtein->getRelativeDistance();
+		$expected = 0.33333333333333;
+		$this->assertEquals($expected, $result, '', $delta);
+	}
+
+	/**
+	 * Tests `getMatrix`.
+	 *
+	 * @return void
+	 */
+	public function testGetMatrix()
+	{
+		list($firstString, $secondString) = $this->getDefaultStrings();
+
+		$DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
+		$actual = $DamerauLevenshtein->getMatrix();
+		$expected = [
+			[0, 1, 2, 3],
+			[1, 1, 2, 3],
+			[2, 2, 2, 3],
+			[3, 3, 3, 3]
+		];
+		$this->assertSame($expected, $actual);
+	}
+
+	/**
+	 * Tests `displayMatrix`.
+	 *
+	 * @return void
+	 */
+	public function testDisplayMatrix()
+	{
+		list($firstString, $secondString) = $this->getDefaultStrings();
+
+		$DamerauLevenshtein = new DamerauLevenshtein($firstString, $secondString);
+		$actual = $DamerauLevenshtein->displayMatrix();
+		$expected = implode('', [
+			"  foo\n",
+			" 0123\n",
+			"b1123\n",
+			"a2223\n",
+			"r3333\n",
+		]);
+		$this->assertSame($expected, $actual);
+	}
+
+	/**
+	 * Returns the default costs.
+	 *
+	 * @return array Costs (insert, delete, substitution, transposition)
+	 */
+	protected function getDefaultCosts()
+	{
+		$insCost = 1;
+		$delCost = 1;
+		$subCost = 1;
+		$transCost = 1;
+
+		return [$insCost, $delCost, $subCost, $transCost];
+	}
+
+	/**
+	 * Returns the default strings.
+	 *
+	 * @return array Strings (foo, bar)
+	 */
+	protected function getDefaultStrings()
+	{
+		$firstString = 'foo';
+		$secondString = 'bar';
+
+		return [$firstString, $secondString];
+	}
 }

src/DamerauLevenshtein.php

Indentation +359 added lines, -359 removed lines

@@ -10,363 +10,363 @@
 class DamerauLevenshtein
 {
 
-    /**
-     * First string.
-     *
-     * @var String
-     */
-    private $compOne;
-
-    /**
-     * Second string.
-     *
-     * @var String
-     */
-    private $compTwo;
-
-    /**
-     * Matrix for Damerau Levenshtein distance dynamic programming computation.
-     *
-     * @var int[][]
-     */
-    private $matrix;
-
-    /**
-     * Boolean flag determining whether is matrix computed for input strings.
-     *
-     * @var bool
-     */
-    private $calculated = false;
-
-    /**
-     * Cost of character insertion (to first string to match second string).
-     *
-     * @var int
-     */
-    private $insCost = 1;
-
-    /**
-     * Cost of character deletion (from first string to match second string).
-     *
-     * @var int
-     */
-    private $delCost = 1;
-
-    /**
-     * Substitution cost.
-     *
-     * @var int
-     */
-    private $subCost = 1;
-
-    /**
-     * Transposition cost.
-     *
-     * @var int
-     */
-    private $transCost = 1;
-
-    /**
-     * Constructor.
-     *
-     * @param string $firstString first string to compute distance
-     * @param string $secondString second string to compute distance
-     * @param int $insCost Cost of character insertion
-     * @param int $delCost Cost of character deletion
-     * @param int $subCost Substitution cost
-     * @param int $transCost Transposition cost
-     */
-    public function __construct($firstString, $secondString, $insCost = 1, $delCost = 1, $subCost = 1, $transCost = 1)
-    {
-        if (!empty($firstString) || !empty($secondString)) {
-            $this->compOne = $firstString;
-            $this->compTwo = $secondString;
-        }
-
-        $this->insCost = $insCost;
-        $this->delCost = $delCost;
-        $this->subCost = $subCost;
-        $this->transCost = $transCost;
-    }
-
-    /**
-     * Returns computed matrix for given input strings.
-     *
-     * @return int[][] matrix
-     */
-    public function getMatrix()
-    {
-        $this->setupMatrix();
-        return $this->matrix;
-    }
-
-    /**
-     * Returns similarity of strings, absolute number = Damerau Levenshtein distance.
-     *
-     * @return int
-     */
-    public function getSimilarity()
-    {
-        if (!$this->calculated) {
-            $this->setupMatrix();
-        }
-
-        return $this->matrix[mb_strlen($this->compOne, 'UTF-8')][mb_strlen($this->compTwo, 'UTF-8')];
-    }
-
-    /**
-     * Procedure to compute matrix for given input strings.
-     *
-     * @return void
-     */
-    private function setupMatrix()
-    {
-        $cost = -1;
-        $del = 0;
-        $sub = 0;
-        $ins = 0;
-        $trans = 0;
-        $this->matrix = [[]];
-
-        $oneSize = mb_strlen($this->compOne, 'UTF-8');
-        $twoSize = mb_strlen($this->compTwo, 'UTF-8');
-        for ($i = 0; $i <= $oneSize; $i += 1) {
-            $this->matrix[$i][0] = $i > 0 ? $this->matrix[$i - 1][0] + $this->delCost : 0;
-        }
-
-        for ($i = 0; $i <= $twoSize; $i += 1) {
-            // Insertion actualy
-            $this->matrix[0][$i] = $i > 0 ? $this->matrix[0][$i - 1] + $this->insCost : 0;
-        }
-
-        for ($i = 1; $i <= $oneSize; $i += 1) {
-            // Curchar for the first string
-            $cOne = mb_substr($this->compOne, $i - 1, 1, 'UTF-8');
-            for ($j = 1; $j <= $twoSize; $j += 1) {
-                // Curchar for the second string
-                $cTwo = mb_substr($this->compTwo, $j - 1, 1, 'UTF-8');
-
-                // Compute substitution cost
-                if ($this->compare($cOne, $cTwo) == 0) {
-                    $cost = 0;
-                    $trans = 0;
-                } else {
-                    $cost = $this->subCost;
-                    $trans = $this->transCost;
-                }
-
-                // Deletion cost
-                $del = $this->matrix[$i - 1][$j] + $this->delCost;
-
-                // Insertion cost
-                $ins = $this->matrix[$i][$j - 1] + $this->insCost;
-
-                // Substitution cost, 0 if same
-                $sub = $this->matrix[$i - 1][$j - 1] + $cost;
-
-                // Compute optimal
-                $this->matrix[$i][$j] = min($del, $ins, $sub);
-
-                // Transposition cost
-                if (($i > 1) && ($j > 1)) {
-                    // Last two
-                    $ccOne = mb_substr($this->compOne, $i - 2, 1, 'UTF-8');
-                    $ccTwo = mb_substr($this->compTwo, $j - 2, 1, 'UTF-8');
-
-                    if ($this->compare($cOne, $ccTwo) == 0 && $this->compare($ccOne, $cTwo) == 0) {
-                        // Transposition cost is computed as minimal of two
-                        $this->matrix[$i][$j] = min(
-                            $this->matrix[$i][$j],
-                            $this->matrix[$i - 2][$j - 2] + $trans
-                        );
-                    }
-                }
-            }
-        }
-
-        $this->calculated = true;
-    }
-
-    /**
-     * Returns maximal possible edit Damerau Levenshtein distance between texts.
-     *
-     * On common substring of same length perform substitution / insert + delete
-     * (depends on what is cheaper), then on extra characters perform insertion / deletion
-     *
-     * @return int
-     */
-    public function getMaximalDistance()
-    {
-        $oneSize = mb_strlen($this->compOne, 'UTF-8');
-        $twoSize = mb_strlen($this->compTwo, 'UTF-8');
-
-        // Max cost, result value
-        $maxCost = 0;
-
-        // Is substitution cheaper that delete + insert?
-        $subCost = min($this->subCost, $this->delCost + $this->insCost);
-
-        // Get common size
-        $minSize = min($oneSize, $twoSize);
-        $maxSize = max($oneSize, $twoSize);
-        $extraSize = $maxSize - $minSize;
-
-        // On common size perform substitution / delete + insert, what is cheaper
-        $maxCost = $subCost * $minSize;
-
-        // On resulting do insert/delete
-        if ($oneSize > $twoSize) {
-            // Delete extra characters
-            $maxCost += $extraSize * $this->delCost;
-        } else {
-            // Insert extra characters
-            $maxCost += $extraSize * $this->insCost;
-        }
-
-        return $maxCost;
-    }
-
-    /**
-     * Returns relative distance of input strings (computed with maximal possible distance).
-     *
-     * @return int
-     */
-    public function getRelativeDistance()
-    {
-        if (!$this->calculated) {
-            $this->setupMatrix();
-        }
-
-        return 1 - (($this->getSimilarity()) / $this->getMaximalDistance());
-    }
-
-    /**
-     * Compares two characters from string (this method may be overriden in child class).
-     *
-     * @param string $firstCharacter First character
-     * @param string $secondCharacter Second character
-     * @return int
-     */
-    protected function compare($firstCharacter, $secondCharacter)
-    {
-        return strcmp($firstCharacter, $secondCharacter);
-    }
-
-    /**
-     * Returns computed matrix for given input strings (For debugging purposes).
-     *
-     * @return string
-     */
-    public function displayMatrix()
-    {
-        $this->setupMatrix();
-
-        $oneSize = mb_strlen($this->compOne, 'UTF-8');
-        $twoSize = mb_strlen($this->compTwo, 'UTF-8');
-
-        $out = '  ' . $this->compOne . "\n";
-        for ($y = 0; $y <= $twoSize; $y += 1) {
-            if ($y - 1 < 0) {
-                $out .= ' ';
-            } else {
-                $out .= (mb_substr($this->compTwo, $y - 1, 1, 'UTF-8'));
-            }
-
-            for ($x = 0; $x <= $oneSize; $x += 1) {
-                $out .= $this->matrix[$x][$y];
-            }
-
-            $out .= "\n";
-        }
-
-        return $out;
-    }
-
-    /**
-     * Returns current cost of insertion operation.
-     *
-     * @return int
-     */
-    public function getInsCost()
-    {
-        return $this->insCost;
-    }
-
-    /**
-     * Sets cost of insertion operation (insert characters to first string to match second string).
-     *
-     * @param int $insCost Cost of character insertion
-     * @return void
-     */
-    public function setInsCost($insCost)
-    {
-        $this->calculated = ($insCost == $this->insCost) ? $this->calculated : false;
-        $this->insCost = $insCost;
-    }
-
-    /**
-     * Returns current cost of deletion operation.
-     *
-     * @return int
-     */
-    public function getDelCost()
-    {
-        return $this->delCost;
-    }
-
-    /**
-     * Sets cost of deletion operation (delete characters from first string to match second string).
-     *
-     * @param int $delCost Cost of character deletion
-     * @return void
-     */
-    public function setDelCost($delCost)
-    {
-        $this->calculated = ($delCost == $this->delCost) ? $this->calculated : false;
-        $this->delCost = $delCost;
-    }
-
-    /**
-     * Returns current cost of substitution operation.
-     *
-     * @return int
-     */
-    public function getSubCost()
-    {
-        return $this->subCost;
-    }
-
-    /**
-     * Sets cost of substitution operation.
-     *
-     * @param int $subCost Cost of character substitution
-     * @return void
-     */
-    public function setSubCost($subCost)
-    {
-        $this->calculated = ($subCost == $this->subCost) ? $this->calculated : false;
-        $this->subCost = $subCost;
-    }
-
-    /**
-     * Returns current cost of transposition operation.
-     *
-     * @return int
-     */
-    public function getTransCost()
-    {
-        return $this->transCost;
-    }
-
-    /**
-     * Sets cost of transposition operation.
-     *
-     * @param int $transCost Cost of character transposition
-     * @return void
-     */
-    public function setTransCost($transCost)
-    {
-        $this->calculated = ($transCost == $this->transCost) ? $this->calculated : false;
-        $this->transCost = $transCost;
-    }
+	/**
+	 * First string.
+	 *
+	 * @var String
+	 */
+	private $compOne;
+
+	/**
+	 * Second string.
+	 *
+	 * @var String
+	 */
+	private $compTwo;
+
+	/**
+	 * Matrix for Damerau Levenshtein distance dynamic programming computation.
+	 *
+	 * @var int[][]
+	 */
+	private $matrix;
+
+	/**
+	 * Boolean flag determining whether is matrix computed for input strings.
+	 *
+	 * @var bool
+	 */
+	private $calculated = false;
+
+	/**
+	 * Cost of character insertion (to first string to match second string).
+	 *
+	 * @var int
+	 */
+	private $insCost = 1;
+
+	/**
+	 * Cost of character deletion (from first string to match second string).
+	 *
+	 * @var int
+	 */
+	private $delCost = 1;
+
+	/**
+	 * Substitution cost.
+	 *
+	 * @var int
+	 */
+	private $subCost = 1;
+
+	/**
+	 * Transposition cost.
+	 *
+	 * @var int
+	 */
+	private $transCost = 1;
+
+	/**
+	 * Constructor.
+	 *
+	 * @param string $firstString first string to compute distance
+	 * @param string $secondString second string to compute distance
+	 * @param int $insCost Cost of character insertion
+	 * @param int $delCost Cost of character deletion
+	 * @param int $subCost Substitution cost
+	 * @param int $transCost Transposition cost
+	 */
+	public function __construct($firstString, $secondString, $insCost = 1, $delCost = 1, $subCost = 1, $transCost = 1)
+	{
+		if (!empty($firstString) || !empty($secondString)) {
+			$this->compOne = $firstString;
+			$this->compTwo = $secondString;
+		}
+
+		$this->insCost = $insCost;
+		$this->delCost = $delCost;
+		$this->subCost = $subCost;
+		$this->transCost = $transCost;
+	}
+
+	/**
+	 * Returns computed matrix for given input strings.
+	 *
+	 * @return int[][] matrix
+	 */
+	public function getMatrix()
+	{
+		$this->setupMatrix();
+		return $this->matrix;
+	}
+
+	/**
+	 * Returns similarity of strings, absolute number = Damerau Levenshtein distance.
+	 *
+	 * @return int
+	 */
+	public function getSimilarity()
+	{
+		if (!$this->calculated) {
+			$this->setupMatrix();
+		}
+
+		return $this->matrix[mb_strlen($this->compOne, 'UTF-8')][mb_strlen($this->compTwo, 'UTF-8')];
+	}
+
+	/**
+	 * Procedure to compute matrix for given input strings.
+	 *
+	 * @return void
+	 */
+	private function setupMatrix()
+	{
+		$cost = -1;
+		$del = 0;
+		$sub = 0;
+		$ins = 0;
+		$trans = 0;
+		$this->matrix = [[]];
+
+		$oneSize = mb_strlen($this->compOne, 'UTF-8');
+		$twoSize = mb_strlen($this->compTwo, 'UTF-8');
+		for ($i = 0; $i <= $oneSize; $i += 1) {
+			$this->matrix[$i][0] = $i > 0 ? $this->matrix[$i - 1][0] + $this->delCost : 0;
+		}
+
+		for ($i = 0; $i <= $twoSize; $i += 1) {
+			// Insertion actualy
+			$this->matrix[0][$i] = $i > 0 ? $this->matrix[0][$i - 1] + $this->insCost : 0;
+		}
+
+		for ($i = 1; $i <= $oneSize; $i += 1) {
+			// Curchar for the first string
+			$cOne = mb_substr($this->compOne, $i - 1, 1, 'UTF-8');
+			for ($j = 1; $j <= $twoSize; $j += 1) {
+				// Curchar for the second string
+				$cTwo = mb_substr($this->compTwo, $j - 1, 1, 'UTF-8');
+
+				// Compute substitution cost
+				if ($this->compare($cOne, $cTwo) == 0) {
+					$cost = 0;
+					$trans = 0;
+				} else {
+					$cost = $this->subCost;
+					$trans = $this->transCost;
+				}
+
+				// Deletion cost
+				$del = $this->matrix[$i - 1][$j] + $this->delCost;
+
+				// Insertion cost
+				$ins = $this->matrix[$i][$j - 1] + $this->insCost;
+
+				// Substitution cost, 0 if same
+				$sub = $this->matrix[$i - 1][$j - 1] + $cost;
+
+				// Compute optimal
+				$this->matrix[$i][$j] = min($del, $ins, $sub);
+
+				// Transposition cost
+				if (($i > 1) && ($j > 1)) {
+					// Last two
+					$ccOne = mb_substr($this->compOne, $i - 2, 1, 'UTF-8');
+					$ccTwo = mb_substr($this->compTwo, $j - 2, 1, 'UTF-8');
+
+					if ($this->compare($cOne, $ccTwo) == 0 && $this->compare($ccOne, $cTwo) == 0) {
+						// Transposition cost is computed as minimal of two
+						$this->matrix[$i][$j] = min(
+							$this->matrix[$i][$j],
+							$this->matrix[$i - 2][$j - 2] + $trans
+						);
+					}
+				}
+			}
+		}
+
+		$this->calculated = true;
+	}
+
+	/**
+	 * Returns maximal possible edit Damerau Levenshtein distance between texts.
+	 *
+	 * On common substring of same length perform substitution / insert + delete
+	 * (depends on what is cheaper), then on extra characters perform insertion / deletion
+	 *
+	 * @return int
+	 */
+	public function getMaximalDistance()
+	{
+		$oneSize = mb_strlen($this->compOne, 'UTF-8');
+		$twoSize = mb_strlen($this->compTwo, 'UTF-8');
+
+		// Max cost, result value
+		$maxCost = 0;
+
+		// Is substitution cheaper that delete + insert?
+		$subCost = min($this->subCost, $this->delCost + $this->insCost);
+
+		// Get common size
+		$minSize = min($oneSize, $twoSize);
+		$maxSize = max($oneSize, $twoSize);
+		$extraSize = $maxSize - $minSize;
+
+		// On common size perform substitution / delete + insert, what is cheaper
+		$maxCost = $subCost * $minSize;
+
+		// On resulting do insert/delete
+		if ($oneSize > $twoSize) {
+			// Delete extra characters
+			$maxCost += $extraSize * $this->delCost;
+		} else {
+			// Insert extra characters
+			$maxCost += $extraSize * $this->insCost;
+		}
+
+		return $maxCost;
+	}
+
+	/**
+	 * Returns relative distance of input strings (computed with maximal possible distance).
+	 *
+	 * @return int
+	 */
+	public function getRelativeDistance()
+	{
+		if (!$this->calculated) {
+			$this->setupMatrix();
+		}
+
+		return 1 - (($this->getSimilarity()) / $this->getMaximalDistance());
+	}
+
+	/**
+	 * Compares two characters from string (this method may be overriden in child class).
+	 *
+	 * @param string $firstCharacter First character
+	 * @param string $secondCharacter Second character
+	 * @return int
+	 */
+	protected function compare($firstCharacter, $secondCharacter)
+	{
+		return strcmp($firstCharacter, $secondCharacter);
+	}
+
+	/**
+	 * Returns computed matrix for given input strings (For debugging purposes).
+	 *
+	 * @return string
+	 */
+	public function displayMatrix()
+	{
+		$this->setupMatrix();
+
+		$oneSize = mb_strlen($this->compOne, 'UTF-8');
+		$twoSize = mb_strlen($this->compTwo, 'UTF-8');
+
+		$out = '  ' . $this->compOne . "\n";
+		for ($y = 0; $y <= $twoSize; $y += 1) {
+			if ($y - 1 < 0) {
+				$out .= ' ';
+			} else {
+				$out .= (mb_substr($this->compTwo, $y - 1, 1, 'UTF-8'));
+			}
+
+			for ($x = 0; $x <= $oneSize; $x += 1) {
+				$out .= $this->matrix[$x][$y];
+			}
+
+			$out .= "\n";
+		}
+
+		return $out;
+	}
+
+	/**
+	 * Returns current cost of insertion operation.
+	 *
+	 * @return int
+	 */
+	public function getInsCost()
+	{
+		return $this->insCost;
+	}
+
+	/**
+	 * Sets cost of insertion operation (insert characters to first string to match second string).
+	 *
+	 * @param int $insCost Cost of character insertion
+	 * @return void
+	 */
+	public function setInsCost($insCost)
+	{
+		$this->calculated = ($insCost == $this->insCost) ? $this->calculated : false;
+		$this->insCost = $insCost;
+	}
+
+	/**
+	 * Returns current cost of deletion operation.
+	 *
+	 * @return int
+	 */
+	public function getDelCost()
+	{
+		return $this->delCost;
+	}
+
+	/**
+	 * Sets cost of deletion operation (delete characters from first string to match second string).
+	 *
+	 * @param int $delCost Cost of character deletion
+	 * @return void
+	 */
+	public function setDelCost($delCost)
+	{
+		$this->calculated = ($delCost == $this->delCost) ? $this->calculated : false;
+		$this->delCost = $delCost;
+	}
+
+	/**
+	 * Returns current cost of substitution operation.
+	 *
+	 * @return int
+	 */
+	public function getSubCost()
+	{
+		return $this->subCost;
+	}
+
+	/**
+	 * Sets cost of substitution operation.
+	 *
+	 * @param int $subCost Cost of character substitution
+	 * @return void
+	 */
+	public function setSubCost($subCost)
+	{
+		$this->calculated = ($subCost == $this->subCost) ? $this->calculated : false;
+		$this->subCost = $subCost;
+	}
+
+	/**
+	 * Returns current cost of transposition operation.
+	 *
+	 * @return int
+	 */
+	public function getTransCost()
+	{
+		return $this->transCost;
+	}
+
+	/**
+	 * Sets cost of transposition operation.
+	 *
+	 * @param int $transCost Cost of character transposition
+	 * @return void
+	 */
+	public function setTransCost($transCost)
+	{
+		$this->calculated = ($transCost == $this->transCost) ? $this->calculated : false;
+		$this->transCost = $transCost;
+	}
 }