Я пытаюсь найти близлежащие повторяющиеся значения в наборе полей, чтобы позволить администратору очистить их.
Есть два критерия, по которым я
Код псевдо-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), это просто не масштабируется для более крупных наборов значений, и кажется, что значительная часть времени обработки тратится просто на итерации через массивы.
Некоторые свойства нескольких наборов значений, которыми управляют
Всего | Строки | Количество совпадений в строке | |
Строки | С матчи | Среднее | Медиана | Макс | Время (ы) |
-------- + -------------- + --------- + -------- + ------ + ---------- +
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 }
Вы можете сначала упорядочить строки по длине (O (N)), а затем проверить только маленькие строки, чтобы они были подстроками или большими строками, плюс только проверить с levenshtein в парах строк, для которых разница не слишком велика.
Вы уже выполняете эти проверки, но теперь вы делаете это для всех пар N x N, в то время как предварительный выбор по длине поможет вам сначала свести пары для проверки. Избегайте цикла N x N, даже если он содержит только те тесты, которые потерпят неудачу.
Для подстрочного соответствия вы можете улучшить его, создав индекс для всех более мелких элементов и обновите его соответствующим образом, когда будете разбирать более крупные элементы. Индекс должен формировать ветвление древовидной структуры на буквах, где каждое слово (строка) формирует путь от корня до листа. Таким образом, вы можете найти, если какое-либо из слов в индексе сравнивается с некоторой строкой. Для каждого символа в строке соответствия попытайтесь продолжить любые указатели в индексе дерева и создать новый указатель на индекс. Если указатель не может перейти к следующему символу в индексе, вы его удалите. Если какой-либо указатель достигает листовой заметки, вы нашли совпадение подстроки. Реализовать это, я думаю, не сложно, но и не тривиально.
Вы можете получить мгновенное 100% -ное улучшение, затянув внутренний контур. Вы не получаете дубликаты матчей в своих результатах?
Для этапа препроцесса я бы прошел и вычислил частоты символов (если ваш набор символов невелик, как a-z0-9, что, учитывая, что вы используете stripos, я думаю, что это возможно). Затем вместо сравнения последовательностей (дорогих) сравните частоты (дешевые). Это даст вам ложные срабатывания, с которыми вы можете либо жить, либо подключаться к тесту, который вы в настоящее время получили.