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案例摺疊）
• src/regexp.c的實現運行5966 LoC（7652包括註釋和空白）

但是，如果您正在尋找'複雜'的算法（例如， Boyer Moore）你不會找到它，因爲坦率地說，在一個文件中查找文本並不需要它。基於vim-7.3.547在debian

現在，如果你想看看最高性能的搜索算法，你可能想看看GNU grep的來源，而不是... :)

---

所有計數軟件包檔案