提高文本处理的性能

Question

我编写了一个程序,指示文本中所需单词类的所有实例.我是这样做的:

从整个文本中创建一个单词数组
迭代这个数组.对于每个单词,看看它的第一个字母是什么.
- 跳转到所选单词类(例如"S")的所有单词的对象中的相应数组并迭代它.如果找到该单词则中断并将其推入匹配数组中.
检查完所有单词后,迭代匹配数组并突出显示文本中的每个单词.

包含240000个单词的文本在100秒内处理有关名词的事项,约4.5秒处理关于我机器上的介词.

我正在寻找一种提高性能的方法,这些是我能提出的想法:

那些坚实的想法是否有更多的想法或经过验证的技术来改进这种处理？

Answer 1

使用javascript的力量.

它使用字符串键作为基本操作来操作字典.对于每个单词类,构建一个对象,每个可能的单词是一个键,一些简单的值,如true或1.然后检查每个单词是简单的typeof(wordClass[word]) !== "undefined".我希望这会快得多.

正则表达式是Javascript的另一个高度优化的区域.您可以将整个事物作为每个单词类的一个大型正则表达式来完成.如果您的突出显示是HTML格式,那么您也可以在RE上使用替换来获得结果.这项工作可能取决于你的单词集有多大.

Answer 2

我建议的解决方案是实现一个trie数据结构.实现需要更多的努力,但与哈希表(字典)相比有几个优点.

查找特里结构中的数据最多需要O(k)时间,其中k是搜索字符串的长度.使用哈希表,将每个单词存储为键可能有效,但是您将哪些值存储为表中该键的值？对于这个问题,哈希表似乎对我来说效率不高.

此外,trie可以通过预订遍历以原生方式提供键输入的字母顺序.哈希表不能.要对其键进行排序,您必须自己实现一个排序功能,这只会增加更多的时间和空间.

如果你进一步阅读尝试,你会遇到后缀树和基数树,它们解决了你想要解决的确切问题.因此,从某种意义上说,你正在重新发明轮子,但我并不是说这是一件坏事.学习这些东西会让你成为更好的程序员.

我们可以将一个简单的trie实现为一组存储三条信息的连接节点:1)符号(字符),2)指向该节点的第一个子节点的指针,以及3)指向父节点的下一个子节点的指针.

class TrieNode {
  constructor(symbol) {
    this.symbol = symbol;
    this.child = null;
    this.next = null;
  }
}

然后,您可以构建一个单词网络,通过单词中的每个字母链接在一起.共享相同前缀的单词通过子指针和下一个指针本地链接在一起,因此查找非常快.我鼓励你进一步研究尝试.它们是整洁的数据结构,我认为它最适合您的问题.