Эффективный алгоритм сопоставления строк

Question

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

Вот мои требования:

• Для данного доменного имени, например, www.example.com, определите, соответствует ли оно имени в списке записей.
• Записи могут быть абсолютными совпадениями, например, www.example.com.
• Записи могут включать символы подстановки, например *.example.com.
• Подстановочные знаки совпадают с наиболее определенного уровня и выше. Например, *.example.com будет соответствовать www.example.com, example.com и sub.www.example.com.
• Записи с подстановочными знаками не встроены, т. Е. Sub. *. Example.com не будет записью.

Язык / среда: C# (.Net Framework 3.5)

Я рассмотрел разбиение записей (и поиск домена) на массивы, изменение порядка, а затем итерацию по массивам. Хотя точный, он чувствует себя медленно.

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

Мой вопрос: каков эффективный способ найти, если строка в форме доменного имени соответствует какой-либо строке в списке строк, учитывая приведенное выше описание?

Answer 1

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

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

Единственные различия между этим и обычным деревом проверки орфографии:

1. Соответствие должно быть сделано в обратном порядке
2. Вы должны принять во внимание подстановочные знаки

Чтобы обратиться к пункту №2, вам просто нужно проверить наличие символа "*" в конце теста.

Быстрый пример:

Записи:

*.fark.com
www.cnn.com

Дерево:

m -> o -> c -> . -> k -> r -> a -> f -> . -> *
                \
                 -> n -> n -> c -> . -> w -> w -> w

Проверка www.blog.fark.com будет включать в себя трассировку по дереву до первого "*", Потому что обход закончился на "*" есть совпадение.

Проверка www.cern.com не будет выполнена на втором "n" из n,n,c,...

Проверка dev.www.cnn.com также не удалась бы, так как обход заканчивается символом, отличным от "*",

Answer 2

Я хотел бы использовать Regex, просто убедитесь, что выражение скомпилировано один раз (вместо того, чтобы вычисляться снова и снова).

Answer 3

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

Каким-то образом три или суффикс дерева выглядит наиболее подходящим.

Если список доменов известен во время компиляции, вы можете посмотреть на токенизацию в '.' и используя несколько машин, сгенерированных gperf.

Ссылки: Google для Trie http://marknelson.us/1996/08/01/suffix-trees/

Answer 4

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

Создайте дерево таким образом, чтобы "com", "net" и т. Д. Были записями верхнего уровня, "example" - на следующем уровне, и так далее. Вам понадобится специальный флаг, чтобы отметить, что узел является подстановочным знаком.

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

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

Кроме того, я хотел бы поспорить, что этот подход будет быстрее, чем RegEx.

Answer 5

Похоже, у вас есть четко определенный набор правил относительно того, что вы считаете верным вводом - вы можете рассмотреть для этого использование для этого рукописного синтаксического анализатора LL. Такие парсеры относительно легко написать и оптимизировать. Обычно у вас есть парсер, который выводит древовидную структуру, описывающую входные данные - я бы использовал это дерево в качестве входных данных для соответствующей процедуры, которая выполняет работу по сопоставлению дерева со списком записей, используя правила, которые вы описали выше.

Вот статья о парсерах рекурсивного спуска.

Answer 6

Я бы попробовал комбинацию попыток с сопоставлением длинного префикса (который используется в маршрутизации для IP-сети). Направленные ациклические графы слов могут быть более подходящими, чем попытки, если пространство является проблемой.

Answer 7

Я собираюсь предложить альтернативу подходу древовидной структуры. Создайте сжатый индекс вашего списка доменов, используя преобразование Берроуза-Уилера. См. http://www.ddj.com/architect/184405504?pgno=1 для полного объяснения техники.

Answer 8

Предполагая, что правила, как вы сказали: буквальный или начинаются с *.

Джава:

public static boolean matches(String candidate, List<String> rules) {
    for(String rule : rules) {
        if (rule.startsWith("*")) {
            rule = rule.substring(2);
        }
        if (candidate.endsWith(rule)) {
            return true;
        }
    }
    return false;
}

Это масштабируется до количества правил, которые у вас есть.

РЕДАКТИРОВАТЬ:

Просто чтобы быть ясно здесь.

Когда я говорю "сортировать правила", я действительно имею в виду создание дерева из символов правил.

Затем вы используете строку соответствия, чтобы попытаться пройтись по дереву (то есть, если у меня есть строка xyz, я начинаю с символа x и проверяю, есть ли у него ветвь y, а затем a z child).

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

Если у вас много (много) правил, я бы отсортировал правила.

Для совпадений без подстановочных знаков вы выполняете итерацию для каждого символа, чтобы сузить возможные правила (т. Е. Если он начинается с "w", то вы работаете с правилами "w" и т. Д.)

Если это совпадение с подстановочным знаком, вы делаете то же самое, но вы работаете со списком "обратных правил" и просто сопоставляете конец строки с концом правила.

Answer 9

Я полагаю, у меня возникает соблазн ответить на ваш вопрос другим: что вы делаете, если считаете, что вашим узким местом является некое совпадение строк, выходящее за рамки простого сравнения строк? наверняка что-то еще перечислено выше в вашем профилировании производительности?

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

Answer 10

Посмотрите на RegExLib

Answer 11

Не уверен, что ваши идеи были для разделения и повторения, но кажется, что это не будет медленным:

Разделите домены вверх и назад, как вы сказали. Хранилище может быть деревом. Используйте хеш-таблицу для хранения ДВУ. Ключом может быть, например, "com", а значения - это хеш-таблица субдоменов под этим TLD, повторяемая до тошноты.

Answer 12

Учитывая ваши требования, я думаю, что вы на правильном пути, думая о работе от конца строки (TLD) к имени хоста. Вы могли бы использовать регулярные выражения, но поскольку вы на самом деле не используете мощь регулярных выражений, я не понимаю, почему вы захотите понести их стоимость. Если вы перевернете строки, станет более очевидно, что вы действительно ищете совпадение префиксов ("*.example.com" становится: "is 'moc.elpmaxe' начало моей входной строки?), Что, безусловно, не не требует чего-то такого сложного, как регулярные выражения.

Какая структура используется для хранения вашего списка записей, во многом зависит от того, насколько большой список и как часто он меняется... для огромного стабильного списка дерево / дерево может быть наиболее эффективным; часто меняющемуся списку нужна структура, которую легко инициализировать / обновить и т. д. Без дополнительной информации я не хотел бы предлагать какую-либо одну структуру.

Answer 13

Изучите алгоритмы KMP (Кнут-Моррис-Пратт) или BM (Бойер-Мур). Они позволяют искать строку быстрее, чем линейное время, за счет небольшой предварительной обработки. Как отмечают другие, удаление главной звездочки, конечно, имеет решающее значение.

Одним из источников информации для них является:

KMP: http://www-igm.univ-mlv.fr/~lecroq/string/node8.html

БМ: http://www-igm.univ-mlv.fr/~lecroq/string/node14.html

Answer 14

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

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

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