Fuzzy Matching Addresses

Question

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

Однако это очень медленно, так как в худшем случае он должен сравнивать каждый старый адрес с каждым новым адресом.

Мое текущее решение заключается в следующем:

matches = []; 
foreach ($classifications as $classification) 
{ 
    $classification = $stringMatchingService->standardize($classification, $stringMatchingService->isClassification()); 
    $shortest = -1; 
    $closest = ''; 
    $cnt = 0; 
    foreach ($lines as $line) 
    { 
     $line = $stringMatchingService->standardize($line, $stringMatchingService->isRTT()); 
     if ($classification[CLASSIFICATION_POSTCODE] != $line[RTT_POSTCODE]) { 
      continue; 
     } 

     $lev = levenshtein($classification[CLASSIFICATION_SUBURB], $line[RTT_SUBURB]); 
    if ($lev == 0) { 
     $matches[$classification[CLASSIFICATION_SUBURB]] = $line[RTT_SUBURB]; 
     $cnt++; 
     break; 
    } 

    if ($lev <= $shortest || $shortest < 0) { 
     //set the closest match and distance 
     $closest = $line[RTT_SUBURB]; 
     $shortest = $lev; 
    } 

    if ($cnt == count($lines)) { 
     $matches[$classification[CLASSIFICATION_SUBURB]] = $closest; 
    } 
    $cnt++; 
} 

} 
print_r(count($matches)); 

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

Мне интересно, как ускорить это, так как на данный момент это очень дорого или, альтернативно, если есть лучший подход?

Любая помощь с учётом,

Thanks!

EDIT: Размер $ классификации является 12000 строк и размер $ линий 17000 строк. Функция гостирован выглядит следующим образом:

public function standardize($line, $dataSet) 
{ 
    switch ($dataSet) { 
     case self::CLASSIFICATIONS: 
      if (!isset($line[9], $line[10]) || empty($line[9]) || empty($line[10])) { 
       continue; 
      } 
      $suburb = $line[9]; 
      $suburb = strtoupper($suburb); 
      $suburb = str_replace('EXT', '', $suburb); 
      $suburb = str_replace('UIT', '', $suburb); 
      $suburb = preg_replace('/[0-9]+/', '', $suburb); 

      $postCode = $line[10]; 
      $postCode = str_pad($postCode, 4,'0', STR_PAD_LEFT); 
      $line[9] = $suburb; 
      $line[10] = $postCode; 
      return $line; 
     case self::RTT: 
      if (!isset($line[1], $line[0]) || empty($line[1]) || empty($line[0])) { 
       continue; 
      } 
      $suburb = $line[1]; 
      $suburb = strtoupper($suburb); 
      $suburb = str_replace('EXT', '', $suburb); 
      $suburb = str_replace('UIT', '', $suburb); 
      $suburb = preg_replace('/[0-9]+/', '', $suburb); 
      $postCode = $line[0]; 
      $postCode = str_pad($postCode, 4,'0', STR_PAD_LEFT); 
      $line[1] = $suburb; 
      $line[0] = $postCode; 
      return $line; 
    } 

Он просто стремится получить доступ к данным надлежащим образом и удалить определенные ключевые слова и колодки почтовые коды, если не в формате XXXX.

Answer 1

Проблема здесь для каждой линии $classifications, вы проверяете соответствие линии в $line. = 12000 * 17000 ...

Итак, я не знаю структуры ваших массивов, но вы можете себе представить, как использовать array_filter.

$matches = array_filter($classifications, function ($entry) use ($lines) { 

    foreach ($lines as $line) 
    { 
     $lev = levenshtein($entry[CLASSIFICATION_SUBURB], $line[RTT_SUBURB]); 

     // if match, return true 
    } 

}); 

$matches будет представлять собой массив согласованных линий.

Это зависит от вашей структуры данных, но лучший способ заключается в использовании в сочетании с array_mergearray_unique

Answer 2

Что толерантность вы использовали для алгоритма расстояние Левенштейна? По моему опыту, менее 0,8 вернет слишком много ложных матчей. Я закончил использование ручных исправлений для коротких слов, таких как raod = road, иначе оценка была бы 1 char неправильной, что сделало бы ее 75%. Я нашел статью для 12 tests to find addresses using fuzzy matching, которая может быть полезна для улучшения вашего алгоритма. Примеры включают в себя:

1. орфографические ошибки
2. Missing Space
3. Неверный тип (улица против Road)
4. граничащий/Соседние пригорода
5. Сокращения
6. Синонимы: пол против уровня
7. Unit , Квартира или квартира против письма
8. Число против письма
9. Дополнительные слова (например,Передняя дверь, отдел Имя)
10. обмениваемого Письма
11. Sounds Like
12. токенизации (Different порядка ввода