Nic*_*one 7 c++ string linguistics
到目前为止,我决定拿一本字典并遍历整个事情.每当我看到换行符时,我都会创建一个包含该换行符的字符串到下一个换行符,然后我执行string.find()以查看该英语单词是否在某处.这需要非常长的时间,每个单词大约需要1/2-1/4秒来验证.
它工作得很好,但我需要每秒检查数千个单词.我可以运行几个窗口,这不影响速度(多线程),但它仍然只检查10秒.(我需要数千)
我正在编写代码来预编译一个包含英语中每个单词的大数组,这应该可以加快它的速度,但仍然没有达到我想要的速度.有有是一个更好的方式来做到这一点.
我正在检查的字符串将如下所示:
"hithisisastringthatmustbechecked"
但大多数都包含完整的垃圾,只是随机字母.
我不能检查不可能的字母组合,因为'tm'之间的'tm'会抛出那个字符串.
您可以使用Knuth-Morris-Pratt(KMP)算法加快搜索速度.
浏览每个字典单词,并为其构建搜索表.你只需要做一次.现在,您对单个单词的搜索将以更快的速度进行,因为"错误的开始"将被消除.
有很多策略可以快速做到这一点。
想法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.
这是一些快速的字符匹配，而且由于某种原因确实很方便，但我今天却无法理解。