Алгоритм сопоставления с образцом

Question

Фон

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

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

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

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

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

Вопросы

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

Есть мысли ...?

Answer 1

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

Answer 2

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

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

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

и т. Д.