Как разбить данный текст на слова из словаря?

Question

Это вопрос интервью. Предположим, у вас есть строка text и dictionary (набор строк). Как разбить text на подстроки так, чтобы каждая подстрока находилась в dictionary.

Например, вы можете разбить "thisisatext" на ["this", "is", "a", "text"], используя /usr/share/dict/words.

Я полагаю, что возврат может решить эту проблему (в псевдо-Java):

void solve(String s, Set<String> dict, List<String> solution) {
   if (s.length == 0)
      return
   for each prefix of s found in dict
      solve(s without prefix, dict, solution + prefix)
}

List<String> solution = new List<String>()
solve(text, dict, solution)

Имеет ли это смысл? Не могли бы вы оптимизировать шаг поиска префиксов в словаре? Какие структуры данных вы бы порекомендовали?

Answer 1

В этом блог-посте содержится очень подробное описание решения этой проблемы.

Основная идея состоит в том, чтобы просто запомнить функцию, которую вы написали, и у вас будет O (n ^ 2) время, O (n) пробел.

Answer 2

Это решение предполагает существование структуры данных Trie для словаря. Далее, для каждого узла в Trie предполагается выполнение следующих функций:

1. node.IsWord (): возвращает true, если путь к этому узлу - слово
2. node.IsChild (char x): возвращает true, если существует дочерний элемент с меткой x
3. node.GetChild (char x): возвращает дочерний узел с меткой x

Function annotate( String str, int start, int end, int root[], TrieNode node):
i = start
while i<=end:
    if node.IsChild ( str[i]):
        node = node.GetChild( str[i] )
        if node.IsWord():
            root[i+1] = start
        i+=1
    else:
        break;

end = len(str)-1
root = [-1 for i in range(len(str)+1)]
for start= 0:end:
    if start = 0 or root[start]>=0:
        annotate(str, start, end, root, trieRoot)

index  0  1  2  3  4  5  6  7  8  9  10  11
str:   t  h  i  s  i  s  a  t  e  x  t
root: -1 -1 -1 -1  0 -1  4  6 -1  6 -1   7

Я оставлю часть для вас, чтобы перечислить слова, которые составляют строку, путем обратного обхода корня.

Сложность по времени равна O (nk), где n - длина строки, а k - длина самого длинного слова в словаре.

PS: Я предполагаю следующие слова в словаре: это, есть, текст, съел.

Answer 3

Подход 1- Три выглядит здесь как нельзя кстати. Создать три слова в английском словаре. Это временное здание стоит один раз. После построения trie ваш string может быть легко сравнен буква за буквой. если в какой-то момент вы встретите лист в дереве, вы можете предположить, что нашли слово, добавьте его в список и продолжайте свой обход. Делайте обход, пока не достигнете конца своего string. Список выводится.

Сложность времени для поиска - O (длина слова).

Сложность пространства - O (charsize * word_length * no_words). Размер вашего словаря.

Подход 2 - Я слышал о Суффикс-деревьях , никогда не использовал их, но это может быть полезно здесь.

Подход 3 - - более педантичная и паршивая альтернатива. Вы уже предложили это.

Вы можете попробовать другой способ. Прогон через dict - проверка на совпадение подстроки. Здесь я предполагаю, что ключи в dict являются words английского словаря /usr/share/dict/words. Так что код псевдо выглядит примерно так -

(list) splitIntoWords(String str, dict d)
{
    words = []
    for (word in d)
    {
        if word in str
            words.append(word);
    }
    return words;
}

Сложность - O (n) проходит через весь dict + O (1) для совпадения подстроки.

Пробел - наихудший случай O (n), если len(words) == len(dict)

Как уже отмечали другие, это требует возврата.

Answer 4

Вы можете решить эту проблему, используя Динамическое программирование и Хеширование .

Вычислить хэш каждого слова в словаре.Используйте хеш-функцию, которая вам нравится больше всего.Я бы использовал что-то вроде (a1 * B ^ (n - 1) + a2 * B ^ (n - 2) + ... + an * B ^ 0)% P, где a1a2 ... an - строка, n- длина строки, B - основание многочлена, а P - большое простое число.Если у вас есть хеш-значение строки a1a2 ... an, вы можете вычислить хеш-значение строки a1a2 ... ana (n + 1) за постоянное время: (hashValue (a1a2 ... an) * B + a(n + 1))% P.

Сложность этой части составляет O (N * M), где N - количество слов в словаре, а M - длина самого длинного слова в словаре..

Затем используйте функцию DP следующим образом:

   bool vis[LENGHT_OF_STRING];
   bool go(char str[], int length, int position)
   {
      int i;

      // You found a set of words that can solve your task.
      if (position == length) {
          return true;
      }

      // You already have visited this position. You haven't had luck before, and obviously you won't have luck this time.
      if (vis[position]) {
         return false;
      }
      // Mark this position as visited.
      vis[position] = true;

      // A possible improvement is to stop this loop when the length of substring(position, i) is greater than the length of the longest word in the dictionary.
      for (i = position; position < length; i++) {
         // Calculate the hash value of the substring str(position, i);
         if (hashValue is in dict) {
            // You can partition the substring str(i + 1, length) in a set of words in the dictionary.
            if (go(i + 1)) {
               // Use the corresponding word for hashValue in the given position and return true because you found a partition for the substring str(position, length).
               return true;
            }
         }
      }

      return false;
   }

Сложность этого алгоритма составляет O (N * M), где N - длина строки, а M - этодлина самого длинного слова в словаре или O (N ^ 2), в зависимости от того, закодировано ли улучшение или нет.

Таким образом, общая сложность алгоритма будет: O (N1 * M) + O (N2 * M) (или O (N2 ^ 2)), где N1 - количество слов в словаре, M - длина самого длинного слова в словаре, а N2 - длина строки).

Если вы не можете придумать хорошую хеш-функцию (где нет столкновений), другое возможное решение - использовать Tries или Patricia trie (еслиразмер обычного файла очень велик) (я не смог опубликовать ссылки на эти темы, потому что моя репутация недостаточно высока, чтобы разместить более 2 ссылок).Но если вы используете это, сложность вашего алгоритма будет O (N * M) * O (время, необходимое для поиска слова в трие), где N - длина строки, а M - длина самого длинного слова.в словаре.

Надеюсь, это поможет, и я прошу прощения за мой плохой английский.