查找一个字符串中的所有单词和短语

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) 将字典放入 trie 或前缀树

2) 对于字符串中的每个位置查找合法的通过 trie 查找单词；存储这些

3) 打印所有不重叠单词的组合

这假设像问题中的示例一样您想要保持字母顺序（即您对字谜不感兴趣）。

Answer 2

#!/usr/bin/python3

from itertools import *
from pprint import pprint as pp

读字典，删除我们在英语中从未使用过的所有 1 和 2 个字母的单词：

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)

编辑：射击，您需要在 for 循环中传递一个起点。否则，您将多余地创建大量调用。 Frank 减去 r 减去 n 与 Frank 减去 n 减去 r 相同。设置一个起点可以确保您获得每个子集一次...除了由于双字母引起的重复。也许只是在打印之前将结果存储到哈希表中？啊啊……