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

Question

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

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

Answer 1

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

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

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

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

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

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

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

Answer 2

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

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

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

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

Answer 4

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

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

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

C.

Answer 5

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

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

• Ave -> Avenue
• Rd. -> Дорога

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

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

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

Answer 6

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

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

Вы можете использовать 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% дерева - существенное улучшение по сравнению с проверяя каждый узел!

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

Answer 8

Вы говорите ...

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

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

Answer 9

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