提高文本处理性能

Question

我写了一个程序，可以在文本中标示出所有所需词类的实例。以下是我的做法：

• 从整个文本中创建一个单词数组

• 遍历这个数组。对于每个单词，查看它的第一个字母。

  • 跳转到所选词类的所有单词的对象中相应的数组（例如 'S'），并遍历它。如果找到该单词，则停止遍历并将其推入匹配的数组中。

• 检查完所有单词后，遍历匹配的数组，并在文本中突出显示每个匹配项。

在我的机器上，处理由24万个单词组成的文本，关于名词大约需要100秒，关于介词则只需4.5秒。

我正在寻找一种提高性能的方法，以下是我能想到的想法：

• 重新排列单词列表中每个块中的项目。按照这样的方式排序：如果单词以元音字母开头，则所有具有辅音字母作为第二个字符的项目首先出现，反之亦然。（假设双元音字母或辅音字母的单词很少）
• 将文本分成章节，只处理当前显示的章节。

这些想法可行吗？有没有其他想法或被证明可以提高此类处理性能的技术？

- Wottensprels

---

也许可以使用 Web Worker 分块返回匹配结果，以便您的用户界面可以立即开始高亮显示。 - Malk

“单词类别”是什么定义？这个定义可以在单词中的任何地方找到吗？因为你的逻辑似乎假定单词必须以与“单词类别”的第一个字母相同的字母开头。大小写敏感吗？“单词类别”可以有标点符号或空格吗？ - Nate

相当基础的问题，你在使用 JQuery 吗？如果是的话，你可能想考虑放弃它，因为与原生 JS 相比，性能实际上相当糟糕。 - Brian H.

@Nate 我错了。我不是以英语为母语的人，认为“word class”是正确的术语。我的意思是词性，例如名词、形容词等。 - Wottensprels

@Brian 谢谢。不过我没有使用jQuery。 - Wottensprels

Answer 1

使用JavaScript的强大功能。它将字符串键的字典操作作为基本操作。对于每个单词类别，建立一个对象，其中每个可能的单词都是一个关键字，而一些简单的值如true或1则会有所不同。然后，检查每个单词只需使用typeof(wordClass[word]) !== "undefined"。我预计这将更快。

正则表达式是JavaScript的另一个高度优化的领域。您可以可能将整个单词类别作为一个巨大的正则表达式来完成。如果您的高亮显示在HTML中，则还可以在RE上使用替换来获取结果。这样做的工作很可能取决于您的单词集有多大。

- DrC

---

那些对象是个好主意，我会立刻尝试！我已经以更简单的方式在使用正则表达式，但我会再看一遍。 - Wottensprels

Answer 2

我提出的解决方案是实现一种 trie 数据结构。虽然需要更多的努力去实现，但它比哈希表（字典）有几个优点。

在 trie 中查找数据最多需要 O(k) 的时间，其中 k 是搜索字符串的长度。使用哈希表存储每个单词作为键可能有效，但你要将什么作为该键的值存储在哈希表中呢？对于此问题，哈希表似乎不够高效。

此外，Trie 可以通过先序遍历本地提供关键条目的字母顺序。哈希表则无法提供。要对其键进行排序，您必须自己实现一个排序函数，这只会增加更多的时间和空间。

如果您进一步研究 tries，您会发现 suffix trees 和 radix trees，它们解决了您试图解决的确切问题。因此，在某种程度上，您正在重新发明轮子，但我不认为这是件坏事。学习这些东西可以让您成为一个更好的程序员。

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

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

你可以构建一个单词网络，每个单词都由字母链接在一起。具有相同前缀的单词通过子节点和下一个指针本地链接在一起，因此查找非常快速。我鼓励你进一步了解字典树。它们是很好的数据结构，我认为它最适合你的问题。

- Brett

Answer 3

我认为需要耗费大量计算时间的步骤如下：

• 在全球类容器中搜索特定单词。
• 在源文件中突出与之匹配的单词。

因此，我建议使用更有效的数据结构来存储你的 world class container 和 matches 列表，以使搜索和查找运行更快。

如果我正确理解了你的问题，你只想突出显示那些在 world class list 中的单词。因此，我建议使用布隆过滤器来非常杰出地完成这项工作。 http://en.wikipedia.org/wiki/Bloom_filter Bloom Filter 是一个集合容器，你可以在其中存储任何元素（单词），并检查是否有任何新单词已经在该集合中。速度非常快，很适合大数据处理。

应用案例如下：

• 将单词类别存储在 Bloom Filter 中，命名为 bfWordClass。
• 遍历提取的单词列表，检查每个单词是否是 bfWordClass 的成员（这个操作非常快速且100％准确）。
• 如果单词属于 bfWordClass，则查找文本并进行突出显示。你可以考虑使用另一个数据结构来存储从文档中提取的唯一单词以及在文档中找到的所有索引，以便更快地参考。

- TaoPR

---

布隆过滤器可能会报告假阳性——即它包含一个实际上不存在的元素。只有当它报告不包含某个元素时，你才能确定它确实不包含该元素。 - Palec

Answer 4

“2,40,000个单词确实是在客户端处理的大数据，当您突出显示文本时，这将在JavaScript以及DOM操作方面创建性能问题。如果可能的话，您应该尝试处理更小的数据集，例如页面、段落或章节。

如果您可以或无法减少活动单词集，下面是一些可用于文本处理的优化方法：

将文本存储在DOM中

您可以尝试两种方法：

1. 单个DOM元素包含所有文本，即240,000个单词 2. 多个DOM元素，每个元素包含N个单词，例如每个包含1,000个单词的240个元素。

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

“匹配-突出显示完全输入的单词”

例如，您想在完全输入“Javascript”和“text”后突出显示它们。在这种情况下，如@DrC所提到的，预处理文本以存储关键字与数据将是一个好方法。 为单词生成一个关键字（如果您想进行不区分大小写的匹配或忽略特殊字符等，则可能需要规范化关键字，即“nosql”将成为“NoSQL”或“NOSQL”或“No-SQL”的关键字）。 您的查找对象将如下所示：

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

}

每当搜索一个单词时，您会生成查找所有匹配项的索引的键，并突出显示文本。 匹配-高亮正在输入的单词 对于这种方法，您需要在JavaScript对象中创建基于trie的结构。 另一种方法是根据当前输入的字符串生成和编译基于正则表达式的代码。例如，如果用户键入了“jav”，则正则表达式将为\jav\gi并在整个文本上进行正则表达式匹配。 这两种方法都需要进行性能比较。

- DhruvPathak

Answer 5

• 使用前三个字符作为键，而不是第一个字符。
• 将你的工作分配到许多后台线程中。
• 首先处理可见文本。

- Ginden

Answer 6

我会这样做。

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;

- Henrik Albrechtsson