Найти все слова и фразы из одной строки

Question

Из-за предметной области (надписи на стене) добавлено интересное условие - буквы не могут изменить свой порядок, поэтому это не вопрос анаграмм .

---

Я увидел длинное слово, написанное краской на стене, а теперь вдруг Я хочу все возможные слова и фразы, которые я могу получить из этого слова, нарисовав любую комбинацию букв. В порядке, случайно разделенные пробелами.
Чтобы расширить возможные результаты, сделаем предположение, что для разделения слов не нужно места.
Редактировать : Очевидно, что порядок букв должен соблюдаться (спасибо idz за то, что указал на это). Также фразы могут быть бессмысленными. Вот несколько примеров:

Source word: disestablishment 
paint out:   ^ ^^^    ^^^^ ^^
left:         i   tabl    e    -> i table

or paint out:^^^^^^^^^   ^ ^^
left:                 ish e    -> i she  (spacelessness is ok)

Визуальный пример Сложный режим / бонусное задание: учтите возможные незначительные изменения букв (D <-> B, C <-> O и т. Д.)

Пожалуйста, предложите свои варианты решения этой проблемы.

Вот мой общий простой подход

Понятно, что для поиска слов нам понадобится английский словарь.
Наша цель - найти слова для поиска в словаре.
Нам нужно найти все возможные варианты букв, чтобы сопоставить их со словарем: каждая буква может быть самой (1) или закрашенной (0).
Принимая во внимание условие «пробел не нужен для разделения слов», чтобы различать слова, мы должны предположить, что между любыми двумя буквами может быть пробел (1 - пробел, 0 - нет).

d i s e s t a b l i s h m e n t
 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^  - possible whitespace

N = количество букв в исходном слове
N-1 = количество возможных пробелов
Любой из элементов N + N - 1 может находиться в двух состояниях, поэтому давайте рассматривать их как логические значения. Количество возможных вариаций составляет 2^(N + N - 1). Да, он считает бесполезные варианты, такие как вставка пробела между пробелами, но я не придумал более элегантную формулу.
Теперь нам нужен алгоритм, чтобы получить все возможные вариации логической последовательности N+N-1 (я еще не придумал, но слово рекурсия течет в моей голове). Затем замените все 1 на соответствующие буквы (если индекс логического числа нечетный) или пробел (четный)
и 0 с пробелами (нечетные) или ничего (четные). Затем обрежьте начальные и конечные пробелы, разделяйте слова и ищите их в словаре.

Мне не нравится этот чудовищный подход и надеюсь, что вы поможете мне найти хорошие альтернативы.

Answer 1

1) Поместите свой словарь в дерево три или префикса

2) Для каждой позиции в строке найдите допустимые слова по trie look up;сохраните их

3) Распечатайте все комбинации непересекающихся слов

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

Answer 2

#!/usr/bin/python3

from itertools import *
from pprint import pprint as pp

Прочитайте в словаре, удалите все одно- и двухбуквенные слова, которые мы никогда не используем в английском языке:

with open('/usr/share/dict/words') as f:
    english = f.read().splitlines()

english = map(str.lower, english)
english = [w for w in english if (len(w)>2 or w in ['i','a','as','at','in','on','im','it','if','is','am','an'])]

def isWord(word):
    return word in english

Ваша проблема:

def splitwords(word):
    """
        splitwords('starts') -> (('st', 'ar', 'ts'), ('st', 'arts'), ('star', 'ts'), ('starts'))
    """
    if word=='':
        yield ()
    for i in range(1,len(word)+1):
        try:
            left,right = word[:i],word[i:]
            if left in english:
                for reading in list(splitwords(right)):
                    yield (left,) + tuple(reading)
            else:
                raise IndexError()
        except IndexError:
            pass

def splitwordsWithDeletions(word):
    masks = product(*[(0,1) for char in word])
    for mask in masks:
        candidate = ''.join(compress(word,mask))
        for reading in splitwords(candidate):
            yield reading

for reading in splitwordsWithDeletions('interesting'):
    print(reading)

Результат (занимает около 30 секунд):

()                                                                                                                                                                                                                    
('i',)
('in',)
('tin',)
('ting',)
('sin',)
('sing',)
('sting',)
('eng',)
('rig',)
('ring',)
('rein',)
('resin',)
('rest',)
('rest', 'i')
('rest', 'in')
...
('inters', 'tin')
('inter', 'sting')
('inters', 'ting')
('inter', 'eng')
('interest',)
('interest', 'i')
('interest', 'in')
('interesting',)

Ускорение возможно, возможно, путем предварительного вычисления того, какие слова можно прочитать на каждой букве, в одну ячейку на букву и итерацию с теми, которые предварительно рассчитаны, чтобы ускорить процесс. Я думаю, что кто-то другой наметит решение на этот счет.

Answer 3

Есть и другие места, где можно найти алгоритмы анаграммы .

subwords(word):
  if word is empty return
  if word is real word:
    print word
  anagrams(word)
  for each letter in word:
    subwords(word minus letter)

Edit: стрелять, вы хотите передать начальную точку для цикла for. В противном случае вы будете избыточно создавать много вызовов. Франк минус г минус п - это то же самое, что Франк минус н минус р. Задание начальной точки может гарантировать, что вы получите каждое подмножество один раз ... За исключением повторов из-за двойных букв. Может быть, просто запишите результаты в хеш-таблицу перед печатью? Argh ...