Какие еще есть алгоритмы сравнения строк?

Question

Есть такая задача: Написать функцию которая на вход принимает два аргумента - строки(отрывки из текста) и сравнивает % совпадения. Если строки идентичны - 100%

Реализовал ее таким образом:

function stringIdentity(string $str1,string $str2){
    $countSameSymbol=0;
    $maxSameSymbol=strlen($str1)>strlen($str2)?strlen($str1):strlen($str2);

    for($i=0;$i<strlen($str1)&&$i<strlen($str2);$i++){
        if($str1[$i]===$str2[$i]){
            $countSameSymbol++;
        }
    }

    return per($maxSameSymbol,$countSameSymbol);
}

//Функция возвращает процент от числа
function per(int $num1,int $num2){
    return $num2/$num1*100;
}

echo stringIdentity("qwert","Qwe rt");

Подскажите пожалуйста какие есть еще алгоритмы сравнения строк?

Answer 1

Можно например используя Алгоритм шинглов Wiki

Вот пример реализации на php

class Shingles {

    // длинна последновательности 
    private $shingles_lenght;

    // символы которые будем игнорить
    private array $filters = ['/,/', '/\./','/:/', '/\?/','/\(/','/\)/', '/-/','/—/', '/;/', '/"/','/\!/', ];

    /**
     * @param int $shingles_lenght
     */
    public function __construct(int $shingles_lenght = 1, array $filters = [])
    {
        $this->setShinglesLenght($shingles_lenght);
        $this->filters = array_merge($this->filters, $filters);
    }

    public function analyze(string $text1, string $text2) {
        $text1 = $this->canonize($text1);
        $text2 = $this->canonize($text2);

        $intersection = array_intersect(
            $this->shinglesGen($text1),
            $this->shinglesGen($text2)
        ) ;
       return  (count($intersection) / count($text1)) * 100 ;
    }

    private function canonize(string $text) {
        $words = explode(' ', preg_replace($this->filters, '', strtolower($text)));
        if(0 === count($words)) {
            return [];
        }
        return array_filter($words, 'strlen');
    }

    private function shinglesGen(array $words) {
        $shingles = [];
        $limit = count($words) - ($this->shingles_lenght - 1);
        for ($i = 0; $i < $limit; $i ++) {
            $array = [];
            for ($j = $i; $j < $i + $this->shingles_lenght; $j ++) {
                $array[] = $words[$j];
            }
            $shingles[] = crc32(implode(' ', $array));
        }
        return $shingles;
    }

    /**
     * @param int $shingles_lenght
     */
    public function setShinglesLenght(int $shingles_lenght): void
    {
        $this->shingles_lenght = $shingles_lenght;
    }

}

Пример сравнения

$shingles = new Shingles();

$text1 = "Первый текст для теста" ;
$text2 = "Второй текст для теста" ;

echo $shingles->analyze($text1, $text2); // 75% 

$shingles->setShinglesLenght(2);
echo $shingles->analyze($text1, $text2); // 50%

$shingles->setShinglesLenght(3);
echo $shingles->analyze($text1, $text2); // 25%

UPD Либо как подсказал @Alexey-Ten - используя Расстояние Левенштейна, в php уже есть реализация этого алгоритма levenshtein()

Если мало - вот еще одна:

function distance($source, $dest) {
    if ($source == $dest) {
        return 0;
    }

    list($slen, $dlen) = [strlen($source), strlen($dest)];

    if ($slen == 0 || $dlen == 0) {
        return $dlen ? $dlen : $slen;
    }

    $dist = range(0, $dlen);

    for ($i = 0; $i < $slen; $i++) {
        $_dist = [$i + 1];
        for ($j = 0; $j < $dlen; $j++) {
            $cost = ($source[$i] == $dest[$j]) ? 0 : 1;
            $_dist[$j + 1] = min(
                $dist[$j + 1] + 1,   // deletion
                $_dist[$j] + 1,      // insertion
                $dist[$j] + $cost    // substitution
            );
        }
        $dist = $_dist;
    }

    return $dist[$dlen];
}

Ну и пример сравнения, находим минимальное к-ство замен и переводим все в проценты

$text1 = "Первый текст для теста" ;
$text2 = "Второй текст для теста" ;

$distance = distance($text1, $text2);
$lenght = max(strlen($text1), strlen($text2));

$percent = 100 - (100 * $distance) / $lenght;

echo $percent; // 82.92%

БЛОГ НА HUSL

Какие еще есть алгоритмы сравнения строк?

Ответы (1 шт):