Обозначить текст в зависимости от определенных правил. Алгоритм в 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-файл и сохранить значения в 'станд :: Карта. Это будет доступно до конца приложения (реализация одноэлементного шаблона).

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

3 - Замените букву «a» на входной текст, поскольку у нас есть токен.

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, производящий токен C-PPA и «что-нибудь еще», производя токен C-PA. Это эффективно структура данных trie.

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

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

Answer 2

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

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

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

Есть некоторые оговорки - в частности, что оба lex и flex генерировать код C, а не C++.

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

Answer 3

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

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

И сделано.

Answer 4

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

Answer 5

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

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

0) создать граф с «начать» вершина

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

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

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