Токенизируйте текст в зависимости от определенных правил. Алгоритм в C ++

Question

Я пишу программу, которая будет маркировать вводимый текст в зависимости от некоторых конкретных правил. Я использую C ++ для этого.

Правила

Letter 'a' should be converted to token 'V-A'
Letter 'p' should be converted to token 'C-PA'
Letter 'pp' should be converted to token 'C-PPA'
Letter 'u' should be converted to token 'V-U'

Это всего лишь пример, и в реальном времени у меня есть около 500 таких правил. Если я предоставляю ввод в виде « appu », он должен маркироваться как « V-A + C-PPA + V-U ». Я реализовал алгоритм для этого и хотел убедиться, что я делаю правильные вещи.

Алгоритм

Все правила будут храниться в файле XML с соответствующим отображением в токене. Что-то вроде

<rules>
  <rule pattern="a" token="V-A" />
  <rule pattern="p" token="C-PA" />
  <rule pattern="pp" token="C-PPA" />
  <rule pattern="u" token="V-U" />
</rules>

1 - при запуске приложения прочитайте этот xml-файл и сохраните значения в ' std :: map '. Это будет доступно до конца приложения (реализация шаблона singleton).

2 - повторять вводимые текстовые символы. Для каждого персонажа ищите совпадение. Если найдено, станьте более жадным и ищите больше совпадений, беря следующие символы из входного текста. Делайте это до тех пор, пока мы не получим совпадение. Поэтому для ввода текста ' appu ' сначала найдите совпадение для ' a '. Если найдено, попробуйте получить больше соответствия, беря следующий символ из входного текста. Поэтому он попытается найти совпадение с ' ap ' и не найдет совпадений. Так что это просто возвращается.

3 - Заменить букву «а» в тексте ввода, когда мы получили для него токен.

4 - Повторите шаги 2 и 3 с оставшимися символами входного текста.

Вот более простое объяснение шагов

input-text = 'appu'
tokens-generated=''

// First iteration
character-to-match = 'a'
pattern-found = true

// since pattern found, going recursive and check for more matches
character-to-match = 'ap'
pattern-found = false

tokens-generated = 'V-A'

// since no match found for 'ap', taking the first success and replacing it from input text
input-text = 'ppu'

// second iteration
character-to-match = 'p'
pattern-found = true

// since pattern found, going recursive and check for more matches
character-to-match = 'pp'
pattern-found = true

// since pattern found, going recursive and check for more matches
character-to-match = 'ppu'
pattern-found = false

tokens-generated = 'V-A + C-PPA'

// since no match found for 'ppu', taking the first success and replacing it from input text
input-text = 'u'

// third iteration
character-to-match = 'u'
pattern-found = true

tokens-generated = 'V-A + C-PPA + V-U'  // we'r done!

Вопросы

1 - Этот алгоритм выглядит хорошо для этой проблемы или есть лучший способ решить эту проблему?

2 - Если это правильный метод, std :: map - хороший выбор здесь? Или мне нужно создать свой собственный контейнер ключ / значение?

3 - Доступна ли библиотека, которая может токенизировать строку, как указано выше?

Любая помощь будет оценена

:)

Answer 1

То есть вы просматриваете все жетоны на вашей карте в поисках совпадений? Вы можете также использовать список или массив; это будет неэффективный поиск, независимо от того.

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

---

Редактировать: позвольте мне объяснить это немного дальше.

Во-первых, я должен объяснить, что я не знаком с этими C ++ std::map, кроме названия, что делает это прекрасным примером того, почему человек изучает теорию этого материала, а также детали конкретных библиотек в Особые языки программирования: если эта библиотека не использует название «карта» (что весьма маловероятно), само имя многое мне говорит о характеристиках структуры данных. Я знаю, например, что будет функция, которая, учитывая один ключ и карту, будет очень эффективно искать и возвращать значение, связанное с этим ключом, и что, скорее всего, есть функция, которая выдаст вам список / array / независимо от всех ключей, которые вы можете искать самостоятельно, используя свой собственный код.

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

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

Так что вам действительно нужна не одна карта, а карты карт, каждая из которых снабжена одним символом. Поиск "p" на верхнем уровне должен дать вам новую карту с двумя ключами: p, производящий токен C-PPA, и "что-нибудь еще", производящий токен C-PA. Это фактически трехуровневая структура данных.

Имеет ли это смысл?

Это может помочь, если вы сначала начнете с написания кода синтаксического анализа следующим образом: представьте, что кто-то другой напишет функции для выполнения нужных вам поисков, и он действительно хороший программист и может творить практически любую магию, которую вы хочу. При написании кода синтаксического анализа сконцентрируйтесь на том, чтобы сделать его как можно более простым и понятным, создавая любой интерфейс с использованием этих произвольных функций, которые вам нужны (не получая ничего тривиального и заменяя все это одной функцией!). Теперь вы можете посмотреть на функции поиска, с которыми вы работали, и это говорит о том, как вам нужен доступ к вашей структуре данных, что приведет вас к нужному типу структуры данных. Как только вы поняли это, вы можете решить, как его загрузить.

Answer 2

Это может показаться немного сложным, но самый эффективный способ сделать это - использовать график для представления диаграммы состояний. Сначала я думал, что boost.statechart поможет, но я подумал, что это не совсем уместно. Этот метод может быть более эффективным, чем использование простого std :: map, если существует много правил, количество возможных символов ограничено, а длина текста для чтения достаточно велика.

Так или иначе, используя простой график:

0) создать граф с "начальной" вершиной

1) читать файл конфигурации xml и создавать вершины, когда это необходимо (переход от одного «набора символов» (например, «pp») к дополнительному (например, «ppa»)). Внутри каждой вершины сохраните таблицу переходов для следующих вершин. Если «ключевой текст» завершен, отметьте вершину как окончательную и сохраните полученный текст

2) Теперь прочитайте текст и интерпретируйте его, используя график. Начните с "стартовой" вершины. (*) Используйте таблицу, чтобы интерпретировать один символ и перейти к новой вершине. Если новая вершина не была выбрана, может быть выдана ошибка. В противном случае, если новая вершина является конечной, выведите полученный текст и вернитесь к начальной вершине. Вернитесь к (*), пока больше не будет текста для интерпретации.

Вы можете использовать boost.graph для представления графика, но я думаю, что он слишком сложен для того, что вам нужно. Создайте свое собственное представление.

Answer 3

Еще лучше, если вы собираетесь использовать библиотеку Boost, всегда есть библиотека Boost Tokenizer -> http://www.boost.org/doc/libs/1_39_0/libs/tokenizer/index.html

Answer 4

Вы можете использовать регулярное выражение (возможно, библиотеку boost :: regex). Если бы все шаблоны были просто цепочками букв, регулярное выражение типа "(a | p | pp | u)" нашло бы жадное совпадение. Итак:

1. Запустите regex_search, используя вышеуказанный шаблон, чтобы найти следующее совпадение
2. Вставьте текст соответствия в вашу std :: map, чтобы получить текст замены.
3. Распечатайте несоответствующий потребляемый ввод и замените текст на вывод, затем повторите 1 на оставшемся вводе.

И готово.

Answer 5

1. Этот метод будет работать - я не уверен, что он эффективен, но он должен работать.

2. Я бы использовал стандартную std :: map вместо вашей собственной системы.

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

Есть некоторые предостережения, в частности, что и lex, и flex генерируют код C, а не C ++.

Я бы также рассмотрел технологию сопоставления с образцом - тот тип вещей, который egrep, в частности, использует. Это имеет то преимущество, что может быть обработано во время выполнения (потому что egrep делает это все время). Или вы можете выбрать язык сценариев - Perl, Python, ... Или вы можете рассмотреть что-то вроде библиотеки PCRE (Perl-совместимые регулярные выражения).