алгоритм разбора строки со словарем

Question

Дано

• словарь, полный слов {in, july, den, dentist, best, ...} с некоторым C ++ API для доступа к нему: boolean findWord(string word) или string getNextWord(void) для его итерации,

• некоторая строка ввода без пробела, например: bestdentistinjuly ...

Вывод

• best dentist in july is... (в основном отдельныйнепустая строка за пробелом, заданная в словаренедостижимая тупиковая проблема.Например, den и dentist являются допустимыми словами для анализа остальной части строки, одно из них может быть просто тупиком.

  Мне кажется, что это жадная проблема или что-то, решаемоединамическое программирование ..

Answer 1

Вы можете создать вид дерева слов:

Вы можете пройти через строку без пробела. Как только вы найдете слово в своем списке, вы добавляете пробел и продолжаете ... пока не сможете идти дальше.

Затем вы возвращаетесь к предыдущему слову и пытаетесь найти, добавляя новые буквы, вы можете создать слова, и если вы можете продолжить их.

Вы пробуете это, пока не попробуете все возможности.

Если вы вернетесь к начальному слову и не найдете никакого решения => нет соль

Вот алгоритм (мой синтаксис псевдокода не очень хорош, но вы можете получить общее представление. Я думаю, вам придется его немного исправить):

TreeWordResult //Tree that keeps the results in memory

Go through the InputString:

      If you find a word in the InputDictionnary 
          Then add this word to the last node of the treeWordResult
      Otherwise:
          while (No word found):
                go back in the treeWordResult
                try to find word in InputDictionnary different from the one before (on the other node)
          endwhile
          if no word found:
                     return NO SOLUTION
          otherwise:
                     continue going through word
          endif
       endif
 return Leaf   

Алгоритм заканчивается, когда вы не находите золь или когда у вас "лист" (вы прошли всю строку)

Вот иллюстрация на вашем примере:

Надеюсь, мои объяснения понятны.

Answer 2

Используйте Trie для хранения словаря. Вы можете увидеть простую реализацию (C #) на Как создать дерево в C #

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

Answer 3

Я думаю, что вы могли бы сделать это быстрее, если бы у вас был метод findWord, возвращающий разные значения для «not-a-word» и «no-words-начиная-with-this-prefix». Это было бы легко, если бы словарь хранился как дерево.

Причина в том, что если вы проверяете слова, как в ответе @Ricky Bobby, после того, как вы найдете «best», вам все равно нужно проверить «bestd» и «bestde» и так далее до конца строки. Однако, если проверка 'bestd' возвращает 'no-long-words', то вы обрезали целую кучу поиска.

Answer 4

Эта проблема в основном похожа на сопоставление регулярного выражения в форме:

(in|july|den|dentis|best|...)*

Таким образом, можно использовать любой алгоритм регулярных выражений.То, что вы должны выбрать, зависит от размера словаря и длины ввода.Вы, вероятно, должны начать здесь: http://en.wikipedia.org/wiki/Regular_expression#Implementations_and_running_times

Answer 5

Возможно, существует несколько допустимых решений для разделения входной строки.Вы можете использовать алгоритм обратного отслеживания , чтобы просто найти одно или все действительные решения.На позициях, где возможны два или более слов, например, «den», «dentist», алгоритм должен сначала пробовать более длинные слова.

Словарь словаря должен быть сохранен в Trie длябыстро найдите подходящие слова.

На следующем изображении ascii левая ветвь будет проверяться первой при поиске в глубину , который предпочитает более длинные слова.Решение будет найдено до того, как алгоритм посмотрит на правую ветвь со словом «ден».

        Best
        /   \
   dentist  den
      /
     in
    /
  july

Answer 6

Непонятно из оригинального поста, что именно решать.Я предполагаю, что @Figo ищет что-то похожее на алгоритм сопоставления строк.

Очень хороший ресурс для этого: http://igm.univ -mlv.fr / ~ lecroq / string /