Сравните 5 000 строк с PHP Levenshtein

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

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") проблемой. Только с вашим сравнением брутальной силы m*n.

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

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

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

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

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

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

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

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

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

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

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

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

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

Затем выполнить итерацию с помощью клавиш $mashed.

C.

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