Оптимизация поиска почти повторяющихся значений - PullRequest
Новая
       8

Оптимизация поиска почти повторяющихся значений

1 голос
/ 21 мая 2010

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

Есть два критерия, по которым я соответствую

  1. Одна строка целиком содержится в другой и составляет не менее 1/4 своей длины
  2. Строки имеют расстояние редактирования менее 5% от общей длины двух строк

Псевдо-PHP код: 

foreach($values as $value){
$matches = array();
foreach($values as $match){
  if(
    (
      $value['length'] < $match['length']
      &&
      $value['length'] * 4 > $match['length']
      &&
      stripos($match['value'], $value['value']) !== false
    )
    ||
    (
      $match['length'] < $value['length']
      &&
      $match['length'] * 4 > $value['length']
      &&
      stripos($value['value'], $match['value']) !== false
    )
    ||
    (
      abs($value['length'] - $match['length']) * 20 < ($value['length'] + $match['length'])
      &&
      0 < ($match['changes'] = levenshtein($value['value'], $match['value']))
      &&
      $match['changes'] * 20 <= ($value['length'] + $match['length'])
      )
    ){
      $matches[] = &$match;
    }
}
// output matches for current outer loop value
}

Я пытался сократить вызовы сравнительно дорогих функций stripos и levenshtein, где это возможно, что значительно сократило время выполнения. Однако, как операция O (n ^ 2), она просто не масштабируется до больших наборов значений, и кажется, что значительная часть времени обработки тратится на итерацию массивов.

Некоторые свойства нескольких наборов значений, работающих с 

Total   | Strings      | # of matches per string |          |
Strings | With Matches | Average | Median |  Max | Time (s) |
--------+--------------+---------+--------+------+----------+
    844 |          413 |     1.8 |      1 |   58 |    140   |
    593 |          156 |     1.2 |      1 |    5 |     62   | 
    272 |          168 |     3.2 |      2 |   26 |     10   |
    157 |           47 |     1.5 |      1 |    4 |      3.2 |
    106 |           48 |     1.8 |      1 |    8 |      1.3 |
     62 |           47 |     2.9 |      2 |   16 |      0.4 |

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

Редактировать: Внедренное решение 

// $values is ordered from shortest to longest string length
$values_count = count($values); // saves a ton of time, especially on linux
for($vid = 0; $vid < $values_count; $vid++){
for($mid = $vid+1; $mid < $values_count; $mid++){ // only check against longer strings
  if(
    (
      $value['length'] * 4 > $match['length']
      &&
      stripos($match['value'], $value['value']) !== false
    )
    ||
    (
      ($match['length'] - $value['length']) * 20 < ($value['length'] + $match['length'])
      &&
      0 < ($changes = levenshtein($value['value'], $match['value']))
      &&
      $changes * 20 <= ($value['length'] + $match['length'])
      )
    ){
      // store match in both directions
      $matches[$vid][$mid] = true;
      $matches[$mid][$vid] = true;
    }

}
}
// Sort outer array of matches alphabetically with uksort()
foreach($matches as $vid => $mids){
  // sort inner array of matches by usage count with uksort()
  // output matches
}

Ответы [ 2 ]

0 голосов
/ 21 мая 2010

Вы можете получить мгновенное улучшение на 100%, затянув свой внутренний цикл.Разве вы не получаете повторяющиеся совпадения в своих результатах?

Для этапа предварительной обработки я бы прошел и рассчитал частоту символов (предполагая, что ваш набор символов мал, как a-z0-9, что, учитывая, что выИспользую стрипос, думаю скорее всего).Тогда вместо сравнения последовательностей (дорого) сравнивать частоты (дешево).Это даст вам ложные срабатывания, с которыми вы можете либо смириться, либо подключиться к тесту, который вы сейчас должны отсеять.

0 голосов
/ 21 мая 2010

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

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

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

...