string - 如何确定随机字符串是否听起来像英语？

Question

我有一个基于输入单词列表生成字符串的算法。如何仅分隔听起来像英语单词的字符串？IE。在保留LORD的同时丢弃RDLO。

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

Answer 1

您可以构建一个巨大的英文文本的马尔可夫链。

之后，您可以将单词输入马尔可夫链并检查单词是英语的概率有多高。

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

在页面底部，您可以看到马尔科夫文本生成器。你想要的恰恰相反。

简而言之：马尔可夫链为每个字符存储下一个字符将跟随的概率。如果你有足够的内存，你可以把这个想法扩展到两个或三个字符。

Answer 2

贝叶斯过滤器的简单方法（来自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)]

Answer 3

使用马尔可夫链很容易生成发音为英语的单词。然而，倒退是一个更大的挑战。结果的可接受误差范围是多少？你总是可以有一个常见字母对、三元组等的列表，并以此为基础对其进行评分。

Answer 4

您可以通过将候选字符串标记为二元组（相邻字母对）并根据英语二元组频率表检查每个二元组来解决此问题。

• 很简单：如果频率表上的任何二元组足够低（或完全不存在），则将该字符串视为不可信而拒绝。（字符串包含“QZ”二元组？拒绝！）
• 不太简单：计算整个字符串的整体合理性，例如，每个二元组的频率除以该长度的有效英语字符串的平均频率的乘积。这将允许您（a）在其他高频二元组中接受具有奇数低频二元组的字符串，以及（b）拒绝具有多个单独的低但不完全低于阈值二元组的字符串.

其中任何一个都需要对阈值进行一些调整，第二种技术比第一种更需要。

用三元组做同样的事情可能会更健壮，尽管它也可能会导致一组更严格的“有效”字符串。这是否成功取决于您的应用程序。

基于现有研究语料库的二元表和三元表可以免费或购买（我没有找到任何免费可用的，但到目前为止只是粗略的谷歌），但你可以从任何好的地方自己计算一个二元表或三元表 -大小的英文文本语料库。只需将每个单词作为标记并计算每个二元组——您可以将其作为散列处理，其中给定的二元组作为键，递增的整数计数器作为值。

英语形态学和英语语音学（众所周知！）不如等距，因此这种技术很可能会生成“看起来”是英语但呈现麻烦发音的字符串。这是三元组而不是二元组的另一个论据——如果 n-gram 跨越整个声音，那么通过分析使用多个字母顺序产生给定音素的声音所产生的怪异将会减少。（例如，想想“犁”或“海啸”。）

Answer 5

我很想在英语单词词典上运行 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）。如果您想了解失败率，您可能需要记录被拒绝的单词并手动验证它们。

Answer 6

您应该研究“可发音的”密码生成器，因为它们正在尝试完成相同的任务。

Perl 解决方案是Crypt::PassGen，您可以使用字典对其进行训练（因此，如果需要，您可以将其训练成各种语言）。它遍历字典并收集关于 1、2 和 3 个字母序列的统计数据，然后根据相对频率构建新的“单词”。

Answer 7

Metaphone和Double Metaphone与 SOUNDEX 类似，只是它们可能比SOUNDEX更接近您的目标。它们被设计为根据它们的语音“声音”“散列”单词，并且擅长为英语（但不是其他语言和专有名称）这样做。

这三种算法要记住的一点是，它们对单词的第一个字母非常敏感。例如，如果您想弄清楚KEAL是否听起来像英语，您将找不到与REAL的匹配项，因为首字母不同。

Answer 8

它们必须是真正的英文单词，还是只是看起来像是英文单词的字符串？

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

或者您可以只使用字典并拒绝不在其中的单词（允许复数和其他变体）。

Answer 9

您可以将它们与字典（在 Internet 上免费提供）进行比较，但这在 CPU 使用率方面可能会很昂贵。除此之外，我不知道有任何其他编程方式可以做到这一点。

Answer 10

这听起来像是一项相当复杂的任务！在我的脑海中，辅音音素在它之前或之后都需要一个元音。但是，确定音素是什么将非常困难！您可能需要手动写出它们的列表。例如，“TR”可以，但“TD”不行，等等。

Answer 11

我可能会根据英语单词数据库使用 SOUNDEX 算法评估每个单词。如果您在 SQL 服务器上执行此操作，那么设置一个包含大多数英语单词列表的数据库（使用免费提供的字典）应该很容易，并且 MSSQL 服务器已将 SOUNDEX 实现为可用的搜索算法。

显然，如果你愿意，你可以用任何语言自己实现它——但这可能是一项艰巨的任务。

通过这种方式，您可以评估每个单词在多大程度上听起来像一个现有的英语单词（如果有的话），并且您可以为您希望接受的结果设置一些限制。您可能想考虑如何组合多个单词的结果，并且您可能会根据测试调整接受限制。

Answer 12

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

Answer 13

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

例如，除了一些双元音和标准辅音对（例如 th、ie 和 ei、oo、tr）外，英语发音词倾向于遵循元音-辅音-元音的模式。使用这样的系统，您应该删除几乎所有听起来不像是英语的单词。仔细检查后，您会发现您可能会删除很多听起来也像英语的单词，但是您可以开始添加允许更广泛单词的规则并手动“训练”您的算法。

您不会删除所有的假阴性（例如，我认为您无法想出一个规则来包含“节奏”而不明确编码该节奏是一个词），但它将提供一种过滤方法。

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