截至目前，我决定拿一本字典并遍历整个内容。每次看到换行符时，我都会创建一个包含从该换行符到下一个换行符的字符串，然后执行 string.find() 以查看该英文单词是否在其中。这需要很长时间，每个单词大约需要每秒 1/2-1/4 秒来验证。
它运行良好，但我需要每秒检查数千个单词。我可以运行几个窗口，这不会影响速度（多线程），但它仍然只能每秒检查 10 个。（我需要数千）
我目前正在编写代码来预编译一个包含英语中每个单词的大型数组，这应该会加快速度，但仍然没有达到我想要的速度。必须有更好的方法来做到这一点。
我正在检查的字符串如下所示：
"hithisisastringthatmustbechecked"
但其中大多数包含完整的垃圾，只是随机字母。
我无法检查不可能的字母组合，因为在“thatmust”之间，该字符串会因为“tm”而被丢弃。
您可以使用Knuth–Morris–Pratt (KMP) 算法来加快搜索速度。
浏览每个字典单词，并为它建立一个搜索表。你只需要做一次。现在，您对单个词的搜索将以更快的速度进行，因为“错误开始”将被消除。
有很多策略可以快速做到这一点。
理念一
获取您正在搜索的字符串，并从某个列开始复制每个可能的子字符串并继续整个字符串。然后将每一个存储在一个以它开头的字母为索引的数组中。（如果一个字母被使用两次，则存储较长的子串。
所以数组看起来像这样：
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 or b or j”可能的字母，然后在“b”之后有“i or o”可能的字母。
正则表达式看起来有点像： /(arun)|(b(ill(y+))|(o(b|dy)))|(jose)/ （尽管我可能漏掉了括号）。这给出了将其创建为正则表达式的要点。
构建此结构后，从第一列开始将其应用于字符串。尝试通过检查替代方案来运行匹配，如果匹配，则试探性地向前移动并尝试箭头后面的字母及其替代方案。如果您到达星号/星号，则匹配。如果您用完了包括回溯在内的备选方案，则移至下一列。
这是很多工作，但有时可以很方便。
旁注我以前通过编写一个程序来构建其中一个，该程序编写了直接运行算法的代码，而不是让代码查看二叉树数据结构。
将每组垂直条选项视为switch针对特定字符列的语句，并且每个箭头都变成嵌套。如果只有一个选项，则不需要完整的switch声明，只需if.
那是一些快速的字符匹配，并且出于某种今天让我难以理解的原因非常方便。
布隆过滤器怎么样？
Bloom filter 由 Burton Howard Bloom 在 1970 年构思，是一种节省空间的概率数据结构，用于测试元素是否是集合的成员。假阳性匹配是可能的，但假阴性是不可能的；即查询返回“在集合内（可能是错误的）”或“绝对不在集合内”。元素可以添加到集合中，但不能删除（尽管这可以通过“计数”过滤器来解决）。添加到集合中的元素越多，误报的概率就越大。
该方法可以按如下方式工作：您创建要检查的一组单词（仅执行一次），然后您可以快速对每个子字符串运行“in/not-in”检查。如果结果是“不在”，您可以安全地继续（布隆过滤器不会给出假阴性）。如果结果是“in”，则运行更复杂的检查以确认（布隆过滤器可能会给出误报）。
据我了解，一些拼写检查器依靠布隆过滤器来快速测试您的最新单词是否属于已知单词词典。
此代码已从如何将没有空格的文本拆分为单词列表？：
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，因为它会将所有内容拆分为单字母单词）。
从理论上讲，我认为您应该能够训练马尔可夫模型并使用它来确定字符串是可能是句子还是可能是垃圾。这样做是为了识别单词而不是句子还有另一个问题：如何确定随机字符串是否听起来像英语？
句子训练的唯一区别是您的概率表会更大一些。但是，根据我的经验，现代台式计算机具有足够的 RAM 来处理马尔可夫矩阵，除非您正在对整个国会图书馆进行培训（这是不必要的——即使是 5 本书左右不同作者的书也应该足以进行非常准确的分类） .
由于您的句子是在没有明确的单词边界的情况下混合在一起的，这有点棘手，但好消息是马尔可夫模型不关心单词，只关心后面的内容。因此，您可以通过首先从训练数据中去除所有空格来使其忽略空格。如果你打算使用爱丽丝梦游仙境作为你的训练文本，第一段可能看起来像这样：
爱丽丝开始厌倦了坐在银行里的姐姐身边，而且她一无所有
它看起来很奇怪，但就马尔可夫模型而言，它与经典实现的区别很小。
我看到您担心时间：培训可能需要几分钟（假设您已经编译了黄金标准“句子”和“随机加扰字符串”文本）。您只需要训练一次，您可以轻松地将“训练过的”模型保存到磁盘，并通过从磁盘加载将其重新用于后续运行，这可能需要几秒钟。对字符串进行调用将需要非常少量的浮点乘法来获得概率，因此在完成训练后，它应该非常快。