Алгоритм для соответствия шаблону

Question

История вопроса

Я проектирование приложение, которое будет преобразовывать текст с одного языка на другой. Например, текст ввода hello будет преобразован в указанный текст языка. Это делается с помощью таблицы поиска для каждого языка. Алгоритм преобразования имеет следующие шаги.

1. Ищет точное совпадение. Весь образ hello будет образцом. Если найдено совпадение, прекратите обработку и верните совпадение.
2. Else начинайте с левого-правого и просматривайте каждый символ до тех пор, пока все комбинации не будут выполнены. Пример: Iteration1: pattern = h, 2nd - he, 3rd - hel и так далее. Согласованный токен будет храниться во временном буфере и возвращаться, когда совпадений больше нет. Это работает как максимальное правило munch.
3. Если совпадение найдено, согласованный текст будет удален из исходного текста и продолжит обработку оставшимся текстом.

Этот алгоритм должен будет многократно перебирать текст ввода и приводить к квадратичной сложности. Я пытаюсь оптимизировать это, упорядочив таблицу поиска в древовидной структуре (очень похоже на дерево суффикса). Если есть поиск текст для h, hel, lo, она будет организована как

root 
--h 
----hel 
--lo 

это поможет мне избежать ненужного поиска. После сопоставления h мне нужно перейти к следующему символу, только если узел h имеет детей. Это значительно сокращает число итераций.

Вопросы

1. Что такое название такого рода структуры данных? Есть ли готовая реализация для C или C++?
2. Вы видите какие-либо возможные улучшения в вышеупомянутом алгоритме или структуре данных?

Любые мысли ...?

Answer 1

Посмотрите на структуру данных «Trie».

Почему бы не использовать Lucene, что индексы текста в очень быстрый способ, и даже больше - индексация включает в себя алгоритмы для

• steming
• предохранитель соответствие

и так далее.

Answer 2

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