我有一种算法，可以根据输入单词列表生成字符串。如何仅将听起来像英语单词的字符串分开？ IE。保留RDLO的同时丢弃RDLO。

编辑：为了澄清，它们不必是词典中的实际单词。他们只需要听起来像英语。例如，KEAL将被接受。

解决方案

使用马尔可夫链很容易产生英语发音的单词。但是，倒退更具挑战性。结果的可接受误差范围是多少？我们总是可以找到常用字母对，三重字母等的列表，然后根据这些字母对它们进行评分。

我们可以将它们与字典(可以在Internet上免费获得)进行比较，但是就CPU使用率而言，这可能是昂贵的。除此之外，我不知道有任何其他编程方式可以做到这一点。

我们可以构建庞大的英文文本的马尔可夫链。

之后，我们可以将单词输入到markov链中，并检查单词是英语的可能性有多大。

看到这里：http://en.wikipedia.org/wiki/Markov_chain

在页面底部，我们可以看到markov文本生成器。我们想要的恰恰相反。

简而言之：markov链为每个字符存储下一个字符将跟随的概率。如果我们有足够的内存，则可以将此想法扩展为两个或者三个字符。

它们必须是真实的英语单词，还是仅仅是看起来像可能是英语单词的字符串？

如果他们只需要看起来像可能的英语单词，则可以对一些真实的英语文本进行统计分析，并找出哪些字母组合经常出现。完成后，我们可以扔掉不太可能的字符串，尽管其中有些可能是真实的单词。

或者，我们可以只使用字典并拒绝其中不存在的单词(允许使用复数形式和其他变体形式)。

听起来这是一项艰巨的任务！在我头顶上，一个辅音音素需要在其之前或者之后的一个元音。但是，确定什么是音素将非常困难！我们可能需要手动写出它们的列表。例如，" TR"可以，但" TD"不可以，等等。

我很想在英语单词的字典上运行soundex算法并缓存结果，然后soundex候选字符串并与缓存匹配。

根据性能要求，我们可以为soundex代码制定距离算法，并接受具有一定容差的字符串。

Soundex非常易于实现，有关该算法的说明，请参阅Wikipedia。

我们要执行的操作的示例实现为：

def soundex(name, len=4):
    digits = '01230120022455012623010202'
    sndx = ''
    fc = ''

    for c in name.upper():
        if c.isalpha():
            if not fc: fc = c
            d = digits[ord(c)-ord('A')]
            if not sndx or (d != sndx[-1]):
                sndx += d

    sndx = fc + sndx[1:]
    sndx = sndx.replace('0','')
    return (sndx + (len * '0'))[:len]

real_words = load_english_dictionary()
soundex_cache = [ soundex(word) for word in real_words ]

if soundex(candidate) in soundex_cache:
    print "keep"
else:
    print "discard"

显然，我们需要提供read_english_dictionary的实现。

编辑：" KEAL"示例将很好，因为它与" KEEL"具有相同的soundex代码(K400)。如果我们想了解失败率，可能需要记录拒绝的单词并手动验证它们。

我可能会使用SOUNDEX算法针对英语单词数据库评估每个单词。如果在SQL服务器上执行此操作，则设置包含大多数英语单词列表的数据库(使用免费的字典)应该非常容易，并且MSSQL服务器已将SOUNDEX实现为可用的搜索算法。

显然，我们可以根据需要自己使用任何语言来实现，但这可能是一项艰巨的任务。

这样，我们就可以评估每个单词听起来像一个现有的英语单词(如果有)的程度，并且可以设置一些限制，以限制我们希望接受的结果的最低程度。我们可能要考虑如何合并多个单词的结果，并且可能会根据测试来调整接受限制。

我建议一些简单的规则以及标准的配对和三胞胎会很好。

例如，英语发音的单词倾向于遵循元音-辅音-元音的模式，除了一些双音调和标准辅音对(例如，th，即ei，ei，oo，tr)。使用这样的系统，我们应该删除几乎所有听起来都不像是英语的单词。通过仔细检查，我们会发现我们可能还会去除很多听起来像英语的单词，但是我们可以开始添加规则，以允许更多单词，并手动"训练"算法。

我们不会删除所有错误的否定词(例如，我认为我们无需在没有明确编码的情况下就可以用规则来包含" rythm"的规则)，但是它将提供一种过滤方法。

我还假设我们想要的字符串可能是英语单词(发音时听起来合理)，而不是绝对是具有英语含义的单词的字符串。

贝叶斯过滤器的简单方法(来自http://sebsauvage.net/python/snyppets/#bayesian的Python示例)

from reverend.thomas import Bayes
guesser = Bayes()
guesser.train('french','La souris est rentrée dans son trou.')
guesser.train('english','my tailor is rich.')
guesser.train('french','Je ne sais pas si je viendrai demain.')
guesser.train('english','I do not plan to update my website soon.')

>>> print guesser.guess('Jumping out of cliffs it not a good idea.')
[('english', 0.99990000000000001), ('french', 9.9999999999988987e-005)]

>>> print guesser.guess('Demain il fera très probablement chaud.')
[('french', 0.99990000000000001), ('english', 9.9999999999988987e-005)]

我们应该研究"可发音的"密码生成器，因为它们试图完成相同的任务。

Perl解决方案是Crypt :: PassGen，我们可以使用字典对其进行培训(因此，如果需要，可以将其培训为多种语言)。它遍历字典并收集有关1、2和3个字母的序列的统计信息，然后根据相对频率构建新的"单词"。

Metaphone和Double Metaphone与SOUNDEX相似，不同之处在于它们可能比SOUNDEX更适合目标。他们被设计为根据其语音"声音"来"散列"单词，并且擅长使用英语(但是其他语言和专有名称却不多)。

所有这三种算法要记住的一件事是，它们对我们单词的第一个字母极为敏感。例如，如果我们想弄清楚KEAL是否是英语，我们将找不到与REAL匹配的字母，因为首字母不同。

我们可以通过以下方式解决此问题：将候选字符串标记为相邻字母的双字母对，然后对照英语双字母频率表检查每个双字母。

• 很简单：如果频率表上的任何二元组足够低(或者完全不存在)，则认为该字符串不合理。 (字符串包含一个" QZ"双字？拒绝！)
• 不太简单：用每个二元组的频率除以该长度的有效英语字符串的平均频率的乘积来计算整个字符串的总体合理性。这样一来，我们既可以(a)接受具有奇数个低频二元组的字符串，又可以接受其他一些高频二元组，并且(b)拒绝包含多个单独的低但阈值以下二元组的字符串。

这两种方法都需要对阈值进行一些调整，第二种技术要比第一种更加。

用三字组合做同样的事情可能会更健壮，尽管它也可能导致一组更为严格的"有效"字符串。是否获胜取决于应用程序。

基于现有研究语料库的Bigram和Trigram表可能是免费提供或者购买的(到目前为止，我没有免费提供，但只有一个粗略的Google会提供)，但是我们可以根据自己的意愿从自己的计算出Bigram或者Trigram表，大小的英文文本语料库。只需将每个单词作为标记进行曲柄处理，然后将每个双字母组合起来，我们就可以将其作为一个哈希处理，以给定的双字母组合作为键，并使用递增的整数计数器作为值。

英语形态和英语语音学(著名！)比等轴测少，因此，该技术很可能会生成"看起来"英语但出现麻烦发音的字符串。这是三元组而不是二元组的另一个论点。通过分析依次使用多个字母来产生给定音素的声音所产生的怪异度，如果n-gram跨越整个声音，将会减少。 (例如，以"低谷"或者"海啸"为例。)

我建议看一下phi测试和巧合指数。 http://www.threaded.com/cryptography2.htm