0

Есть такая задача: Написать функцию которая на вход принимает два аргумента - строки(отрывки из текста) и сравнивает % совпадения. Если строки идентичны - 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");

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

3
  • а как считать процент совпадения, если строки не идентичны? "сегодня 17 февраля" и "сегодня - 17 февраля" на сколько процентов совпадения? 17 фев 2022 в 15:14
  • Задал похожий вопрос) На что получил ответ: "Алгоритм полностью лежит на том кто его будет реализовывать." Задача со * 17 фев 2022 в 15:40
  • Ну классика ru.m.wikipedia.org/wiki/…
    – Alexey Ten
    17 фев 2022 в 16:00

1 ответ 1

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%

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.