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

StackOverflow https://stackoverflow.com/questions/92006

  •  01-07-2019
  •  | 
  •  

题

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

编辑： 澄清一下，它们不需要是字典中的实际单词。他们只需要听起来像英语即可。例如 韩国凯尔 会被接受。

有帮助吗？

解决方案

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

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

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

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

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

其他提示

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

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)]

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

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

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

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

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

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

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

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

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

变音位 和 双变音位 与 SOUNDEX 类似，但它们可能比 SOUNDEX 更适合您的目标 声音指数. 。它们被设计为根据单词的语音“声音”来“散列”单词，并且擅长对英语执行此操作（但对于其他语言和专有名称则不然）。

对于这三种算法需要记住的一件事是它们对单词的第一个字母极其敏感。例如，如果您想弄清楚是否 韩国凯尔 听起来是英语，你找不到匹配的 真实的 因为首字母不同。

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

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

Soundex 非常容易实现 - 请参阅 维基百科 获取算法的描述。

您想要执行的操作的示例实现是：

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

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

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

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

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

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

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

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

通过这种方式，您可以评估每个单词听起来有多少与现有的英语单词（如果有）相似，并且您可以设置一些限制来限制您想要接受的结果的低度。您可能想要考虑如何组合多个单词的结果，并且您可能会根据测试调整接受限制。

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

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

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

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

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top