提高文本处理性能

Question

我编写了一个程序，可以指示文本中所需词类的所有实例。我是这样做的：

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

一段包含 240000 个单词的文本在我的机器上处理名词需要 100 秒，处理介词需要大约 4.5 秒。

我正在寻找提高性能的方法，这些是我能想到的想法：

重新排列我的单词列表中每个块中的项目。对它们进行排序，如果单词以声乐开头，则所有以辅音作为第二个字符的项目排在第一位，反之亦然。（假设带有双声母或辅音的单词很少见）
将文本结构化为章节并仅处理当前显示的章节。

这些是可靠的想法吗？是否有更多的想法或成熟的技术来改进这种处理？

Answer 1

发挥javascript的力量。

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

正则表达式是 Javascript 的另一个高度优化的领域。您可能可以将整个事情作为每个单词 class 的一个巨大的正则表达式来完成。如果您的突出显示位于 HTML，那么您也可以只在 RE 上使用替换来获得结果。这项工作可能取决于您的单词集有多大。

Answer 2

我认为计算时间长的步骤是：

正在世界class容器中搜索特定单词。
突出显示源文档中的匹配项。

因此，我会提出一个更有效的数据结构来存储您的 word class container 和 matches 列表。因此搜索和查找运行得更快。

如果我对你的问题理解正确，你只想突出显示世界class列表中的那些词。所以我建议 Bloom Filter，它非常出色地完成了这项工作。

http://en.wikipedia.org/wiki/Bloom_filter

Bloom Filter是一个集合容器，你可以存储任何元素（词）并检查是否有新词已经在这个集合中。速度快得惊人，适合大数据处理。

用例为：

您将单词 classes 存储在布隆过滤器中，我们将其命名为 bfWordClass.
遍历提取的单词列表，检查每个单词是否是 bfWordClass 的成员（此操作非常快且 100% 准确）。
如果单词确实属于 bfWordClass，那么您查找文本并突出显示它们。你可以考虑另一种数据结构来存储从文档中提取的唯一词和文档中找到的所有索引，以便更快地参考。

Answer 3

我会做这样的事情。

HTML

<section id="text">All keywords in this sentence will be marked</section>

JavaScript

element = document.getElementId('text');
text = element.innerHTML;
array_of_keywords = ['keyword', 'will'];
eval('text = text.replace(/(' + array_of_keywords.join('|') + ')/g, "<mark>$1</mark>");');
element.innerHTML = text;

Answer 4

我提出的解决方案是实现一个trie数据结构。它需要更多的努力来实现，但与散列table（字典）相比有几个优点。

在trie中查找数据最多需要O(k)时间，其中k是trie的长度搜索字符串。使用散列 table，将每个单词存储为键可能有效，但是您将什么存储为 table 中该键的值？对于这个问题，哈希 table 对我来说似乎不是很有效。

此外，trie 可以通过预序遍历以本机方式提供按字母顺序排列的键条目。哈希 table 不能。要对其键进行排序，您必须自己实现一个排序功能，这只会增加更多时间和 space.

如果您进一步阅读尝试，您会遇到 suffix trees and radix trees，它解决了您正在尝试解决的确切问题。所以，从某种意义上说，你是在重新发明轮子，但我并不是说这是一件坏事。学习这些东西可以让你成为更好的程序员。

我们可以将一个简单的 trie 树实现为一组连接的节点，这些节点存储三部分信息：1) 一个符号（字符），2) 指向该节点的第一个子节点的指针，以及 3) 指向父节点的下一个子节点。

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

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

Answer 5

使用前 3 个字符作为键，而不是第一个字符。
将您的工作分担给许多 background threads
首先处理可见文本

Answer 6

2,40,000 个单词确实是需要在客户端处理的大数据，这会在 javascript 以及突出显示文本时的 DOM 操作中产生性能问题。如果可能，您应尝试处理较小的集合，例如页面或段落或部分。

如果您可以或不能减少您的活动词组，您可以尝试以下几种优化您的文本处理：

将文本存储在 DOM

您可以在这里尝试两种方法：

包含所有文本的单个 DOM 元素，即 24 万个单词
多个 DOM 个元素，每个元素包含 N 个单词，例如 240 个元素，每个元素包含 1000 个单词。

您将不得不使用像 jsPerf 这样的工具来查看 innerHTML 在这两种方法中的变化速度有多快，即替换单个 DOM 元素中的大 innerHTML 或文本与替换匹配的多个 innerHTML DOM 个元素。

匹配-完全输入时突出显示单词

例如，您希望在完全键入文本后突出显示 "Javascript" 和 "text"。在这种情况下，正如@DrC 提到的那样，预处理您的文本以存储密钥与数据将是一件好事。为单词生成一个键（如果您想要匹配不区分大小写的键，或者忽略特殊字符等，您可能需要规范化键，即 'nosql' 将是 'NoSQL' 或 [=48= 的键] 或 'No-SQL`。您的查找对象将如下所示：

{
  'nosql': {'matches':[{'NoSQL':3},{'NOSQL':6}],  // indexes of strings where this occurs

}

每当搜索一个词时，您都会生成所有匹配项的查找索引的键，并突出显示文本。

匹配-在键入时突出显示单词 对于这种方法，您需要在 javascript 对象中创建一个基于 trie 的结构。另一种方法是基于生成和编译正则表达式当前输入的字符串，例如，如果用户输入 'jav' 则正则表达式为 \jav\gi 并对整个文本进行正则表达式匹配。两种方法都需要进行性能比较

提高文本处理性能

Increasing performance on text processing

javascript

performance

text

process

HTML

JavaScript