linux - VI编辑器中搜索功能背后的算法是什么

Question

即使我打开一个新文件，即使在一个非常大的文件上，搜索命令也能运行得非常快？用于实现它的算法是什么。

我只是好奇？

Answer 1

这只是您的常规正则表达式实现。

首先，模式被编译成正则表达式 ( vim_regcomp)。

接下来，vim_regexec{_multi,_nl,_both}用于执行它。它通过逐步处理各种原子来做到这一点（有一个明确的回溯堆栈）。

现在，正则表达式的叶节点仅由行人功能处理，例如

• vim_strbyte
• vim_strchr

• cstrchr; 例如，这显示了实现的“直截了​​当”（特别是，如果您查看FEAT_MBYTE未定义的更简单的情况）

  /*
  * cstrchr: This function is used a lot for simple searches, keep it fast!
  */
      static char_u *
  cstrchr(s, c)
      char_u  *s;
      int     c;
  {
      char_u  *p;
      int     cc;
  
      if (!ireg_ic
  #ifdef FEAT_MBYTE
              || (!enc_utf8 && mb_char2len(c) > 1)
  #endif
              )
          return vim_strchr(s, c);
  
      /* tolower() and toupper() can be slow, comparing twice should be a lot
      * faster (esp. when using MS Visual C++!).
      * For UTF-8 need to use folded case. */
  #ifdef FEAT_MBYTE
      if (enc_utf8 && c > 0x80)
          cc = utf_fold(c);
      else
  #endif
          if (MB_ISUPPER(c))
          cc = MB_TOLOWER(c);
      else if (MB_ISLOWER(c))
          cc = MB_TOUPPER(c);
      else
          return vim_strchr(s, c);
  
  #ifdef FEAT_MBYTE
      if (has_mbyte)
      {
          for (p = s; *p != NUL; p += (*mb_ptr2len)(p))
          {
              if (enc_utf8 && c > 0x80)
              {
                  if (utf_fold(utf_ptr2char(p)) == cc)
                      return p;
              }
              else if (*p == c || *p == cc)
                  return p;
          }
      }
      else
  #endif
          /* Faster version for when there are no multi-byte characters. */
          for (p = s; *p != NUL; ++p)
              if (*p == c || *p == cc)
                  return p;
  
      return NULL;
  }
  

现在短篇小说是：

• 涉及到正则表达式的实现（因为它支持很多特性，比如 Unicode 大小写折叠）
• 5966 LoC 运行中的实现src/regexp.c（7652 包括注释和空格）

但是，如果您正在寻找“复杂”的算法（例如 Boyer Moore），您将找不到它，因为坦率地说，在单个文件中查找文本并不需要它。

现在，如果您想查看性能最佳的搜索算法，您可能需要查看 GNUgrep的源代码...... :)

---

所有计数均基于vim-7.3.547debian 软件包存档