Алгоритм поиска строки с самым низким частотным символом
У меня есть 3 текстовых файла. Один с набором текста для поиска
(напр. ABCDEAABBCCDDAABC)
Один содержит несколько шаблонов для поиска в тексте
(напр. AB, EA, CC)
И последний, содержащий частоту каждого символа
(Напр.
А 4
Б 4
С 4
D 3
Е 1
)
Я пытаюсь написать алгоритм для нахождения наименее часто встречающегося символа для каждого шаблона и поиска строки для этих случаев, а затем проверяю окружающие буквы, чтобы увидеть, соответствует ли строка. В настоящее время у меня есть символы и частоты в их собственных векторах соответственно. (Где i = 0 для каждого вектора будет A 4 соответственно.
Есть лучший способ сделать это? Может быть, более быстрая структура данных? Кроме того, каковы эффективные способы проверки строки шаблона по фрагменту текстовой строки, когда найдена наименее частая буква?
Решение
Вы можете запустить Ахо-Corasick алгоритм. Его сложность (после предварительной обработки, сложность которой не связана с текстом) Θ (n + p), где
-
N длина текста
-
п общее количество найденных совпадений
Это по сути оптимально. Нет смысла пытаться пропустить буквы, которые кажутся частыми:
-
Если буква не является частью совпадения, алгоритм занимает единицу времени.
-
Если буква является частью совпадения, то совпадение включает в себя все буквы, независимо от их частоты в тексте.
Другие решения
Вы можете запустить итерационный цикл, который ведет подсчет экземпляров и проверяет, появлялся ли символ более, чем в процентах от общего количества искомых символов и общей длины строки. То есть, если у вас есть 100 символов и 5 возможностей, любой символ, появившийся более чем на 20% из ста, может быть сброшен со счетов, что повышает эффективность, передавая любое значение, соответствующее этому.