Сравните 5000 строк с PHP Левенштейна

Question

У меня есть 5000, иногда больше, строки адресов улиц в массиве. Я хотел бы сравнить их всех с Левенштейном, чтобы найти похожие совпадения. Как я могу сделать это, не просматривая все 5000 и не сравнивая их напрямую с другими 4999?

Редактировать: Меня также интересуют альтернативные методы, если у кого-то есть предложения. Общая цель состоит в том, чтобы найти похожие записи (и исключить дубликаты) на основе предоставленных пользователем уличных адресов.

Answer 1

Я думаю, что лучший способ сгруппировать похожие адреса:

1. создать базу данных с двумя таблицами - одна для адреса (и идентификатора), другая для soundexes слов или буквенных чисел в адресе (с внешним ключом таблицы адресов)

2. в верхнем регистре адреса, заменить все, кроме [A-Z] или [0-9] пробелом

3. разделить адрес по пробелам, вычислить soundex каждого «слова», оставить все, что нужно, только с цифрами и сохранить его в таблице soundexes с внешним ключом адреса, который вы начали с

4. для каждого адреса (с идентификатором $ target) найдите наиболее похожие адреса:

   SELECT similar.id, similar.address, count(*) 
   FROM adress similar, word cmp, word src
   WHERE src.address_id=$target
   AND src.soundex=cmp.soundex
   AND cmp.address_id=similar.id
   ORDER BY count(*)
   LIMIT $some_value;
   

5. вычисляет разницу Левенштейна между вашим исходным адресом и несколькими верхними значениями, возвращаемыми запросом.

(любые операции с большими массивами в базах данных выполняются быстрее)

Answer 2

Вы можете использовать bk-tree для ускорения поиска / сравнения.

http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees говорит:

Теперь мы можем сделать особенно полезное наблюдение о расстоянии Левенштейна: оно образует метрическое пространство.
[...]
Предположим, на мгновение у нас есть два параметра: запрос, строка, которую мы используем в нашем поиске, и n максимальное расстояние, на которое строка может быть от запроса и все еще возвращаться. Скажем, мы берем произвольную строку, тестируем и сравниваем ее с запросом. Назовите полученное расстояние d. Поскольку мы знаем, что выполняется неравенство треугольника, все наши результаты должны иметь самое большее расстояние d + n и как минимум расстояние d-n от теста.
[...]
Тесты показывают, что поиск на расстоянии 1 запроса не более 5-8% от дерева и поиск с двумя ошибками запросов не более 17-25% дерева - существенное улучшение по сравнению с проверкой каждого узла!

edit: Но это не поможет вам решить вашу проблему ("12 Bird Road, Apt 6" и "12 Bird Rd. # 6"). Только с вашим грубым сравнением.

Answer 3

Я думаю, что вы не можете избежать обхода массива, поскольку функция levenstein () принимает только строки, а не массив в качестве входных данных.

Вы можете сделать что-то вроде:

for($i=0;$i<count($array)-1;$i++)
{
    for($j=$i+1;$j<count($array);$j++)
    {
        $lev = levenshtein($array[$i],$array[$j]);
        if($lev == 0)
        {
            // exact match
        }
        else if($lev <= THRESHOLD)
        {
            // similar
        }
    }
}

Answer 4

Вы можете сгруппировать их на основе soundexes, а затем ограничить сравнения ближайшими N случаями ...

 $mashed=array();
 foreach ($address as $key=>$val) {
      $mashed[$key]=soundex($val);
 }
 sort($mashed);

Затем перебираем ключи $ mashed.

С

Answer 5

Из-за природы алгоритма Левенштейна (особенно из-за того, что это сравнение двух строк), я не могу понять, как это возможно.

Конечно, вы могли бы сократить количество сравнений, выполнив сначала некоторые базовые требования соответствия, но это выходит за рамки того, о чем вы спрашиваете.

В качестве (вполне возможно, неуместного) варианта вы всегда можете использовать что-то вроде soundex, что позволит вам предварительно вычислить строковые значения. (Вы также можете использовать его непосредственно в MySQL.)

Answer 6

$stringA = "this is php programming language";
$stringB = "this is complete programming script in which java php and  all other minor languages include";

echo "string 1---->".$stringA."<br />";
echo "string 2---->".$stringB."<br />";
// changing string to arrays
$array1 = explode(' ', $stringA);
$array2 = explode(' ', $stringB);

// getting same element from two strings
$c = array_intersect($array1, $array2);
// changing array to the string
$d=implode(' ',$c);

echo "string same elements---> ".$d."<br />";


// getting difrent  element from two arrays
$result = array_diff($array2, $array1);
// changing array to the string
$zem = implode(' ',$result);

if (!empty($zem)) {
  echo "string diffrence---> ".$zem."<br />";
} else {
  echo "string diffrence--->both strings are same <br />";
}

similar_text($stringA, $d, $p);
echo " similarity between the string is ".$p."% <br />";

Answer 7

Если вы хотите найти все похожие значения, вам придется сравнить все элементы со всеми остальными. Но выбор правильных функций массива значительно ускорит процесс. Вот быстрый пример (массив результатов мог бы быть лучше):

$results = array();
$count = count($entries);
while ($count != 0) {
    # The entry to process
    $entry = array_shift($entries);
    # Get levenshtein distances to all others
    $result = array_map(
        'levenshtein',
        # array_map() needs two arrays, this one is an array consisting of
        # multiple entries of the value that we are processing
        array_fill($entry, 0, $count),
        $toCompare
    );
    $results[] = array($entry => $result);
    $count--;
}

Answer 8

Учитывая вашу проблему, я не вижу другого способа, кроме как сравнить каждый адрес с любым другим адресом, если вы хотите использовать Lehvenstein distance .

Прежде всего, вы должны нормализовать адрес, избавиться от сокращений и т. Д.

• пр. -> проспект
• Rd. -> Дорога

Вы можете иметь фиксированное максимальное расстояние Левенштейна ( N ) для аналогичных адресов.

Если это так, вы могли бы прервать алгоритм Лехвенштейна, если уверены, что расстояние редактирования для текущей пары адресов больше, чем N. Для этого вам нужно написать собственную версию алгоритма Лехвенштейна. Это сделает алгоритм немного быстрее.

Есть также некоторые связанные тривиальные оптимизации. Например: если адрес A имеет длину 10 символов, а адрес B имеет длину 20 символов, и вы считаете, что адреса с расстоянием по Левенштейну менее 8 одинаковы. Вы можете посмотреть длины адресов и сразу решить, что они не похожи.