#string #algorithm #string-matching
#строка #алгоритм #сопоставление строк
Вопрос:
Каков простой способ реализовать алгоритм поиска / замены в строке? Я хотел бы преобразовать строку, используя словарь, который определяет правила замены. Проблема в том, что после каждой замены я должен убедиться, что последующие замены работают с исходной строкой. Например:
Моя строка: ABCABCDEFDEF
Мои правила: ABC -> DEF и DEF -> XXX
Итак, мой результат должен быть: DEFDEFXXXXXX, а не XXXXXXXXXXXX (что было бы результатом, если бы я сначала применил первое правило, а затем применил второе правило).
Комментарии:
1. Для каждого правила найдите индексы, в которых оно соответствует тексту. Затем применить правило? (Я думаю, должен быть какой-то более быстрый способ)
2. Ну, после каждого применяемого мной правила мои индексы будут меняться, не так ли?
3. Пройдите всю строку один раз и запишите вхождение требуемых подстрок в список или аналогичную структуру данных. затем выполните итерацию по списку и продолжайте замену!
4. Создайте конечный автомат. Это можно сделать вручную (требуется всего 5 состояний) или с помощью генератора, такого как (f) lex.
Ответ №1:
Простой способ:
-
Начиная с первого символа, попробуйте каждый ключ, если он встречается в этой позиции.
-
Если вы нашли совпадение, замените и продолжите с символом после замены
-
В противном случае продолжайте со следующего символа
Иметь в виду:
-
Неоднозначности: если у вас есть как «AB», так и «ABC» в качестве ключей, вам нужно решить, какой из них должен соответствовать «ABCD». Обычно вы хотите, чтобы более длинная строка соответствовала (в противном случае она никогда не совпадала)
-
Unicode: сначала нормализуйте ключи и исходную строку.
Этого, безусловно, достаточно для нескольких ключей. Однако это O (N * M), где N — длина строки, а M — количество замен.
Улучшения:
-
не выполняйте линейный поиск соответствия; вместо этого используйте отсортированный список ключей и выполните двоичный поиск символа в исходной строке, затем следующего и т. Д. Действительно, может быть полезно запомнить позицию и ключ найденных совпадений только в первом проходе и выполнить замены во втором проходе
-
для больших строк со многими заменами обычно лучше создавать новую строку
-
Используйте Aho-Corasick для поиска. Это использует ограниченное пространство поиска (т.Е. Знания, полученные из списка ключевых слов), чтобы избежать проверки каждого символа исходной строки
Ответ №2:
В зависимости от используемого вами языка могут быть такие предопределенные функции. String.Replace может быть полезно, если вы используете C #. Это сэкономит вам очень много времени. Если вы все еще ищете алгоритмы, которые могут находить шаблоны в других строках, алгоритм Horspool может быть тем, что вы ищете.
Вам все равно придется реализовать логику для последующих замен, чтобы работать с исходной строкой. Но это звучит как несложная задача.
Комментарии:
1. Да, я могу использовать такие функции, как String . Заменить, но я не могу понять, как применять каждое правило независимо.
2. Ну, вы могли бы сохранить индексы подстрок, которые вы уже изменили. В следующий раз, когда вы просматриваете строку для другого шаблона, вы можете посмотреть, была ли подстрока уже изменена.