Алгоритм для анализа строки со словарем

Ответ 1

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

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

Ответ 2

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

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

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

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

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

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

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   

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

Вот пример вашего примера:

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

Ответ 3

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

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

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

Ответ 4

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

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

Ответ 5

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

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

Ответ 6

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

Словарь, конечно, должен храниться в Trie, чтобы быстро найти соответствующие слова.

В следующем изображении ascii левая ветвь будет сначала рассмотрена в Глубино-первый поиск, который предпочитает более длинные слова. Решение будет найдено до того, как алгоритм посмотрит на правую ветвь со словом "den".

        Best
        /   \
   dentist  den
      /
     in
    /
  july