logo标签列表

检查字符串中是否包含英语句子

c++stringlinguistics
7
目前，我决定采用字典并遍历整个字典。每次我看到一个换行符，我就创建一个包含从该换行符到下一个换行符的字符串，然后我使用string.find()来查找该英文单词是否在其中。这需要很长时间，每个单词需要大约1/2至1/4秒才能验证。
它完美地工作，但我需要每秒检查成千上万个单词。我可以运行几个窗口（多线程），但仍然只能检查大约10个单词每秒。（我需要成千上万个）
我正在编写代码以预编译一个包含英语单词的大型数组，这应该会大大加快速度，但仍无法获得所需的速度。一定有更好的方法来做到这一点。
我要检查的字符串将如下所示：
"hithisisastringthatmustbechecked"

但它们大部分都是一些无意义的垃圾文字，只是随机字母的组合。

我无法检查不可能的字母组合，因为在“thatmust”之间有一个“tm”，所以该字符串将被丢弃。

单词之间不能用空格分隔吗？您是否需要验证所有字母组成单词，还是只检测到至少一个英语单词就足够了？您会根据使用频率排序并从最常见的单词开始吗？ - Neil Kirk
1
你实际上想要实现什么？字符串中是否会有空格？你需要完全准确还是概率猜测就可以了？垃圾行是随机字符还是其他的？ - DUman
我首先会生成一个常被引用的非单词缓存 -- 4-6个字符的前缀，这些前缀从未被使用过。有几种方法可以做到这一点。 - Hot Licks
1
我可以看到几种方法来实现它，但我认为关键在于字典数据结构。也许将字典存储为一棵树，每个节点都是一个字母，这样所有通向叶子的路径都会产生一个完整的单词。(例如 h-a-t<-h-a<-h)。然后迭代一次行（从开头到结尾），以查看该子字符串的开头是否是一个单词。如果节点知道到单词的最长路径以便提前退出搜索，则可获得额外奖励分数。 - IdeaHat
对于有效单词的字典，@MadScienceDreams 实际上在描述一种基数树，这是一种表达文本选择的好方法，但创建和维护成本有点高。 - Hot Licks
显示剩余13条评论
5个回答
5
你知道 OP 的 string.find() 没有使用这个算法吗？ - Lee Meador
即使它可以，它也无法重用预先构建的搜索表，并且每次通过“find”函数都必须重新构建它。 - Sergey Kalinichenko
我明白了。我重新阅读了一遍，发现有多个“要搜索”的字符串。除非它们非常长，否则我不愿意尝试替换“内置”搜索函数。这些函数可能在不同于KMP算法的层面上进行了优化。 - Lee Meador
1

有很多快速完成此操作的策略。

方法1

将要搜索的字符串复制，并针对从某列开始到整个字符串结束的每个可能的子字符串进行存储。然后将每个字符串存储在以它开头字母为索引的数组中。（如果字母出现两次，则存储较长的子字符串）。

因此，该数组看起来像这样：

a - substr[0] = "astringthatmustbechecked"
b - substr[1] = "bechecked"
c - substr[2] = "checked"
d - substr[3] = "d"
e - substr[4] = "echecked"
f - substr[5] = null // since there is no 'f' in it
... and so forth

然后，对于字典中的每个单词，在其首字母指示的数组元素中搜索。这限制了需要搜索的内容量。此外，您永远无法在字符串中第一个'r'之前找到以'r'开头的单词。如果字母根本不在那里，有些单词甚至不会进行搜索。

思路2

通过注意字典中最长的单词并从那些数组中的字符串中去除距离该距离更远的字母来扩展该想法。

所以你在数组中有这个：

a - substr[0] = "astringthatmustbechecked"

但如果列表中最长的单词只有5个字母，那么就没有必要保留超过这个长度的任何单词：
a - substr[0] = "astri"

如果某个字母出现多次，你需要保留更多的字母。因此这个例子需要保留整个字符串，因为“e”出现的间隔小于5个字母。

e - substr[4] = "echecked"

你可以通过使用以任何特定字母开头的最长单词来压缩字符串，进一步扩展此功能。 想法3 这与1和2无关。这是一个你可以使用的想法。
你可以将字典转换为存储在链接数据结构中的正则表达式。也可以编写正则表达式，然后应用它。
假设这些是字典中的单词：
arun
bob
bill
billy
body
jose

构建这样的链接结构。（实际上是二叉树，以一种可以解释如何使用它的方式表示。）
a -> r -> u -> n -> *
|
b -> i -> l -> l -> *
|    |              |
|    o -> b -> *    y -> *
|         |
|         d -> y -> *
|
j -> o -> s -> e -> *

箭头表示一个字母必须紧随另一个字母后面。所以"r"必须在"a"之后，否则就无法匹配。
向下的线表示一个选项。你有可能是"a或b或j"的字母，然后在"b"之后是可能的"i或o"的字母。
正则表达式看起来像：/(arun)|(b(ill(y+))|(o(b|dy)))|(jose)/（虽然我可能会打错括号）。这大致说明了如何将其创建为正则表达式。
一旦你建立了这个结构，你就可以从第一列开始将其应用于你的字符串。尝试通过检查备选项来运行匹配，如果有一个匹配，则向前暂时移动并尝试箭头后面的字母及其备选项。如果你到达星号/星号，它就匹配了。如果你用完了备选项，包括回溯，你就移到下一列。
这是很多工作，但有时候会很方便。
附注：我之前写了一个程序，直接编写运行该算法的代码，而不是让代码查看二叉树数据结构。
想象每组垂直条选项都是针对特定字符列的switch语句，每个箭头都变成一个嵌套。如果只有一个选项，您不需要完整的switch语句，只需要一个if。

这是一些快速字符匹配技巧，出于某种原因，它今天很方便。

这是一个很好的想法！我会尝试实现它，如果它能给我所期望的速度，我会接受这个答案。 :) 这个列表包含每种英语语言，而我要检查的字符串并不是很大，所以第二个想法行不通。 - Nicholas Pipitone
如果列表很小，那么这将是有用的，但是当检查整个字典时，几乎每种组合都存在。 - Nicholas Pipitone
但请记住，使用Idea 2，您只能从以特定字母开头的单词数组中搜索任何特定字符串。因此，组合数量并不重要。重要的是，该单词只能匹配在存在该特定字母的位置开始的地方。 - Lee Meador
我已经忘记了5年前写这篇文章时自己在做什么，但我刚好在翻阅旧帖子。有趣的是，5年前我知道的很少，但是使用Trie树解决这个问题非常简单。因为"Idea 3"被接受。 - Nicholas Pipitone
1

这段代码是从如何将没有空格的文本拆分为单词列表？修改而来：

from math import log

words = open("english125k.txt").read().split()
wordcost = dict((k, log((i+1)*log(len(words)))) for i,k in enumerate(words))
maxword = max(len(x) for x in words)

def infer_spaces(s):
    """Uses dynamic programming to infer the location of spaces in a string
    without spaces."""

    # Find the best match for the i first characters, assuming cost has
    # been built for the i-1 first characters.
    # Returns a pair (match_cost, match_length).
    def best_match(i):
        candidates = enumerate(reversed(cost[max(0, i-maxword):i]))
        return min((c + wordcost.get(s[i-k-1:i], 9e999), k+1) for k,c in candidates)

    # Build the cost array.
    cost = [0]
    for i in range(1,len(s)+1):
        c,k = best_match(i)
        cost.append(c)

    # Backtrack to recover the minimal-cost string.
    costsum = 0
    i = len(s)
    while i>0:
        c,k = best_match(i)
        assert c == cost[i]
        costsum += c
        i -= k

    return costsum

使用相同的字典，来测试你的字符串输出

>>> infer_spaces("hithisisastringthatmustbechecked")
294.99768817854056

这里的诀窍在于找到可以使用的阈值，记住使用更小的单词会使成本更高（如果算法找不到可用的单词，则返回inf，因为它会将所有内容拆分为单个字母）。
1

你听说过布隆过滤器吗？

布隆过滤器是由Burton Howard Bloom于1970年提出的一种高效的概率型数据结构，用于测试一个元素是否属于一个集合。可能存在误判，但不会漏判；即查询结果要么是“在集合中（可能错误）”，要么是“绝对不在集合中”。可以向集合中添加元素，但不能删除（这可以通过“计数”过滤器来解决）。添加到集合中的元素越多，误判的概率就越大。

这种方法可以按照以下步骤进行：首先创建要检查的单词集（仅需一次），然后可以快速地运行每个子字符串的“在/不在”检查。如果结果是“不在”，则可以安全地继续（布隆过滤器不会漏判）。如果结果是“在”，则运行更复杂的检查以确认（布隆过滤器可能会误判）。

据我了解，一些拼写检查器依赖布隆过滤器快速测试您最新的单词是否属于已知单词的字典。

你如何使用它？提取OP正在搜索的字符串的每个有效子字符串并将其传递给Bloom过滤器？即使您使用仅关心长度为3及以上且短于字典中最长单词的信息，提取所有这些子字符串似乎也需要很多工作。 - Lee Meador
是的 - 对父字符串进行分词以获取候选子字符串将耗费时间。布隆过滤器只是一个快速测试子字符串是否不在字典中的想法（如果不在，则我们快速进行下一步操作）。 - Escualo
我喜欢这种思路，它可以改变搜索的方式。它不是将所有单词应用于“要搜索”的字符串子串，而是将所有子串应用于要查找的单词列表的表示形式。 - Lee Meador
0

理论上，我认为您应该能够训练一个马尔可夫模型，并使用它来判断一个字符串是否可能是句子或垃圾。还有一个关于识别单词而不是句子的问题：如何确定一个随机字符串听起来像英语？

训练句子的唯一区别在于您的概率表会稍微大一些。但根据我的经验，现代桌面计算机的RAM足以处理马尔可夫矩阵，除非您正在对整个国会图书馆进行训练（这是不必要的-即使通过不同作者写作的五本书应该足以实现非常精确的分类）。

由于您的句子没有明显的单词边界，所以有点棘手，但好消息是马尔可夫模型并不关心单词，只关心跟随什么。因此，您可以让它忽略空格，方法是先从训练数据中删除所有空格。如果您要将爱丽丝漫游奇境记用作训练文本，则第一段可能如下所示：

艾丽丝开始厌倦了坐在河岸旁边陪伴她的姐姐，因为她无事可做。她曾经偷看过姐姐读的书，但里面没有图片或对话，艾丽丝想，没有图片或对话的书有什么用呢？

看起来很奇怪，但就马尔科夫模型而言，这与经典实现的差别微不足道。

我知道你关心时间：训练可能需要几分钟（假设你已经编译好了“句子”和“随机乱序字符串”文本的黄金标准）。你只需要训练一次，可以轻松将“训练好”的模型保存到磁盘上，并通过从磁盘加载重复使用，这可能需要几秒钟的时间。调用一个字符串只需要进行少量的浮点数乘法即可得到概率，因此在完成训练后，它应该非常快速。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接