比正则表达式更快地匹配字符串之间的字符

Faster way match characters between strings than Regex?

本文关键字：字符串 之间 字符 正则表达式      更新时间：2023-09-26

用例是我想将查询字符串与单词数组进行比较，并返回匹配项。匹配是指单词包含查询字符串中的所有字符，顺序无关紧要，重复字符都可以。正则表达式似乎太强大了(只需要锤子的大锤(。我编写了一个解决方案，通过循环访问字符并使用 indexOf 来比较字符，但它似乎一直很慢。(http://jsperf.com/indexof-vs-regex-inside-a-loop/10(正则表达式是此类操作的最快选择吗？有没有办法让我的替代解决方案更快？

 var query = "word",
    words = ['word', 'wwoorrddss', 'words', 'argument', 'sass', 'sword', 'carp', 'drowns'],
    reStoredMatches = [],
    indexOfMatches = [];
  function match(word, query) {
    var len = word.length,
      charMatches = [],
      charMatch,
      char;
    while (len--) {
      char = word[len];
      charMatch = query.indexOf(char);
      if (charMatch !== -1) {
        charMatches.push(char);
      }
    }
    return charMatches.length === query.length;
  }
  function linearIndexOf(words, query) {
    var wordsLen = words.length,
      wordMatch,
      word;
    while (wordsLen--) {
      word = words[wordsLen];
      wordMatch = match(word, query);
      if (wordMatch) {
        indexOfMatches.push(word);
      }
    }
  }
  function linearRegexStored(words, query) {
    var wordsLen = words.length,
      re = new RegExp('[' + query + ']', 'g'),
      match,
      word;
    while (wordsLen--) {
      word = words[wordsLen];
      match = word.match(re);
      if (match !== null) {
        if (match.length >= query.length) {
          reStoredMatches.push(word);
        }
      }
    }
  }

请注意，您的正则表达式是错误的，这肯定是它运行如此之快的原因。

现在，如果您的查询是"word"(如您的示例所示(，则正则表达式将是：

/[word]/g

这意味着查找其中一个字符："w"、"o"、"r"或"d"。如果匹配，则 match(( 返回 true。做。绝对比最肯定更正确的 indexOf(( 快得多。(即，在简单 match(( 调用的情况下，"g"标志将被忽略，因为如果任何一件事匹配，该函数将返回 true。

另外，您提到了任意数量字符的想法/概念，我想如下所示：

'word', 'wwoorrddss'

indexOf(( 肯定不会正确捕获它，如果你真的意味着每个字符的"任何数字"。因为您应该匹配无限数量的案例。像这样的东西作为正则表达式：

/w+o+r+d+s+/g

你肯定很难用普通的JavaScript编写正确的代码，而不是使用正则表达式。但是，无论哪种方式，这都会有些慢。

从下面的评论中，单词的所有字母都是必需的，为此，您必须对 3 个字母的单词进行 3 个测试(3 个阶乘(：

/(a.*b.*c)|(a.*c.*b)|(b.*a.*c)|(b.*c.*a)|(c.*a.*b)|(c.*b.*a)/

显然，阶乘会非常迅速地增加你的可能性数量，并在超长的正则表达式中吹走你的记忆(尽管如果一个单词多次具有相同的字母，你可以简化，但你不必多次测试该字母(。

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
...

这可能就是为什么你在普通 JavaScript 中正确编写的测试要慢得多的原因。

此外，在您的情况下，您应该几乎像在拼字游戏词典中一样编写单词：所有字母都按字母顺序排列(拼字游戏保留重复项(。所以"字"就是"dorw"。正如您在示例中所示，单词"wwoorrddss"将是"dorsw"。你可以有一些后端工具来生成你的单词表(所以你仍然把它们写成"word"和"words"，你的工具会把它们转换为"dorw"和"dorsw"。然后，您可以按字母顺序对正在测试的单词的字母进行排序，结果是您不需要正则表达式的愚蠢阶乘，您可以简单地这样做：

/d.*o.*r.*w/

这将匹配任何包含"单词"的单词，例如"密码"。

对字母进行排序

的一种简单方法是将您的单词拆分为一个字母数组，然后对数组进行排序。您可能仍会收到重复项，这取决于排序功能。(我不认为默认的JavaScript排序会自动删除重复项。

还有一个细节，如果你的测试应该是不区分大小写的，那么你希望在运行测试之前将字符串转换为小写。所以像这样：

query = query.toLowerCase();

在您的顶级功能的早期。

您正在尝试加快算法"单词中的字符是查询字符的子集"。您可以缩短此检查并避免某些分配(这些分配更具可读性，但并非严格需要(。尝试以下版本的匹配

  function match(word, query) {
    var len = word.length;
    while (len--) {
      if (query.indexOf(word[len]) === -1) { // found a missing char
        return false;
      }
    }
    return true; // couldn't find any missing chars
  }

这提供了 4-5 倍的改进

根据应用程序的不同，您可以尝试对单词进行预排序，并将单词中的每个单词预排序为另一种优化。

正则表达式匹配算法构造一个有限状态自动机，并根据从左到右读取的当前状态和字符做出决定。 这包括阅读每个字符一次并做出决定。

对于静态字符串(在几个文本上查看固定字符串(，你有更好的算法，比如 Knuth-Morris 允许你一次比一个字符更快，但你必须明白，这个算法不是用于匹配正则表达式，只是普通字符串。

如果您对Knuth-Morris感兴趣(还有其他几种算法(，请在维基百科中进行一轮。 http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

您可以做的一件好事是调查正则表达式匹配例程是否使用 DFA 或 NDFA 执行此操作，因为 NDFA 占用的内存更少并且更容易计算，但 DFA 做得更快，但会有一些编译惩罚和占用更多的内存。

Knuth-Morris算法还需要在工作之前将字符串编译成自动机，所以如果你只是使用它来查找某个字符串中的一个单词，它可能不适用于你的问题。

相关文章：