你有沒有使用KMP或BM算法？

我知道KMP（Knuth-Morris-Pratt）和BM（Boyers-Moore）算法都是很好的字符串搜索操作算法。我也知道BM比KMP快3-5倍。你有沒有使用KMP或BM算法？

在您的行業軟件編程經驗中，您有沒有使用BM或KMP算法？這個算法真的很重要嗎？

來源

2011-04-09 user699656

我知道KMP代表什麼，但不是BM。你會介意寫下他們每個人所代表的東西，以防其他人不知道嗎？ – Mehrdad 2011-04-09 05:26:31

@Mehrdad：BM可能是Boyer-Moore。 – 2011-04-09 05:27:43

@Mike：啊，謝謝！ – Mehrdad 2011-04-09 05:29:36

如果你看看例如Java的String.indexOf函數，他們似乎使用暴力方法進行字符串匹配。你可能想知道爲什麼。

原因是某些查詢預處理是在這些算法中執行的，而且可能代價高昂（尤其是對於BM，如果您同時使用這兩個數組）。因此，在KMP和BM可以使用強力方法之前，您搜索的字符串必須大一些。

當使用不同的算法並且在處理大字符串時，您可能會考慮對文本進行索引而不是查詢（例如後綴樹）。這在每次處理新文本時甚至會很有用。

在我看來，這些算法相當具有學術性，只在特殊情況下才有用。

來源

2011-04-09 05:37:34 jallmer

謝謝jallmer。好的回答 – user699656 2011-04-09 05:41:24

有趣的是，gcc的'strstr（）'實現（相當於'String.indexOf（）'）使用了一個非常酷的算法，它只需要線性時間，與BM和KMP不同，*常量空間*。這基本上消除了在庫函數中使用樸素O（n^2）方法的任何理由，因爲唯一的情況是速度更快的情況是使用非常短的字符串，其中兩種算法都已經非常快速。（從MAK的回答中得到了這個） – 2011-04-09 13:17:11

實際上，String的* real * indexOf方法通常不是您在JDK源代碼中看到的方法，而是由JDK插入的內部版本，至少在Sun的熱點Java 6和7. 該版本實際上確實使用BM的簡化版本。它僅適用於被檢查字符根本不在字符串中的情況，在這種情況下，通常（參見注釋）會跳過N個字符，其中N是搜索字符串的長度。注意：*通常*進來，因爲算法使用32條目散列表來確定一個字符是否出現在字符串中，因此碰撞是可能的。 – BeeOnRope 2012-12-22 22:25:44

我在硬件上實施了一次KMP。如果硬件是FPGA，則可以使用可重配置功能和自修改電路。這個電路獲取搜索字符串。比在硬件中進行必要的預處理，並將其自身重新配置爲執行KMP的邏輯。但是這裏也需要抓取大量的數據來加快速度，但是有一些事情是這樣的（例如DNA匹配）。

來源

2011-04-09 06:11:56 flolo

感謝flolo，一個很好的經驗分享。 :) – user699656 2011-04-09 06:15:00

glibc的strstr函數是線性的。它使用了Two-Way Algorithm，我認爲這是Boyer-Moore的變種。所以，我想這使得任何在gcc中使用strstr的人實際上都在使用現實世界中的快速字符串搜索算法。對於快速算法是否重要的問題，恕我直言，它只有在數據量足夠大的情況下才有意義。我們所做的很多顯式字符串操作都是在非常小的字符串上（比如少於500個字符）。這並不是說我們不會進行繁重的字符串操作（例如在數據庫上進行全文搜索），但是在這種情況下，我們通常會讓數據庫或圖書館爲我們完成繁重的工作。數據庫或庫使用快速字符串搜索算法 - 所以我不會說它們並不重要，只是它的使用不直接顯示給我們。

來源

2011-04-09 09:04:46 MAK

哇！線性時間和恆定空間，它會打勾所有的盒子！想知道爲什麼我以前沒聽說過這個算法。不得不說，我無法按照http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260上的解釋，所以我下載了Crochemore＆Perrin的1991年論文，但發現它有25個不祥之兆網頁 - 超過了我的「隨意閱讀」門檻。：/有一天...... – 2011-04-09 13:12:52

@j_random_hacker：太難跟我了。我猜它不像KMP或Rabin Karp那麼受歡迎。 – MAK 2011-04-09 13:23:49

你有沒有使用KMP或BM算法？

回答

相關問題