Сравнить 5000 строк с PHP Levenshtein

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

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

2. запишите адрес, замените что-либо, кроме [AZ] или [0-9], пробелом

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

4. для каждого адреса (с id $ 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. вычислить разницу levenstein между вашим исходным адресом и верхними несколькими значениями, возвращаемыми запросом.

(выполнение каких-либо операций на больших массивах часто происходит быстрее в базах данных)

Я думаю, вы не можете избежать цикла через массив, поскольку функция 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 } } } 

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

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

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

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

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

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

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

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

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

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

C.

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

 $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--; } 

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

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

• Ave -> Avenue
• Радиолярии -> Дорога

У вас может быть некоторое фиксированное максимальное расстояние Lehvenstein ( N ) для аналогичных адресов.

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

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

Ты говоришь…

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

Я говорю … используйте методы на http://semaphorecorp.com/mpdd/mpdd.html

 $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 />";