搜索關鍵字列表

Question

我正在構建一個消息傳遞反垃圾郵件解決方案，我必須將每次收到的文本消息與關鍵字列表進行比較，如果文本消息具有列表中的某個關鍵字，我必須將其刪除。

問題是什麼是搜索關鍵字列表的最佳算法？例如低於

text message received is "hi how are you, visit us at www.xyz.com" 

和列表樣品低於

www.abc.com 
www.xyz.com 
... 
... 

Answer 1

多少關鍵字你在說什麼？看看Boyer-Moore字符串搜索算法，它可能適用於您的目的，並且不難實現。下面是來自wikipedia article採取的Java實現：

/** 
    * Returns the index within this string of the first occurrence of the 
    * specified substring. If it is not a substring, return -1. 
    * 
    * @param haystack The string to be scanned 
    * @param needle The target string to search 
    * @return The start index of the substring 
    */ 
    public static int indexOf(char[] haystack, char[] needle) { 
    if (needle.length == 0) { 
     return 0; 
    } 
    int charTable[] = makeCharTable(needle); 
    int offsetTable[] = makeOffsetTable(needle); 
    for (int i = needle.length - 1, j; i < haystack.length;) { 
     for (j = needle.length - 1; needle[j] == haystack[i]; --i, --j) { 
     if (j == 0) { 
      return i; 
     } 
     } 
     // i += needle.length - j; // For naive method 
     i += Math.max(offsetTable[needle.length - 1 - j], charTable[haystack[i]]); 
    } 
    return -1; 
    } 

    /** 
    * Makes the jump table based on the mismatched character information. 
    */ 
    private static int[] makeCharTable(char[] needle) { 
    final int ALPHABET_SIZE = 256; 
    int[] table = new int[ALPHABET_SIZE]; 
    for (int i = 0; i < table.length; ++i) { 
     table[i] = needle.length; 
    } 
    for (int i = 0; i < needle.length - 1; ++i) { 
     table[needle[i]] = needle.length - 1 - i; 
    } 
    return table; 
    } 

    /** 
    * Makes the jump table based on the scan offset which mismatch occurs. 
    */ 
    private static int[] makeOffsetTable(char[] needle) { 
    int[] table = new int[needle.length]; 
    int lastPrefixPosition = needle.length; 
    for (int i = needle.length - 1; i >= 0; --i) { 
     if (isPrefix(needle, i + 1)) { 
     lastPrefixPosition = i + 1; 
     } 
     table[needle.length - 1 - i] = lastPrefixPosition - i + needle.length - 1; 
    } 
    for (int i = 0; i < needle.length - 1; ++i) { 
     int slen = suffixLength(needle, i); 
     table[slen] = needle.length - 1 - i + slen; 
    } 
    return table; 
    } 

    /** 
    * Is needle[p:end] a prefix of needle? 
    */ 
    private static boolean isPrefix(char[] needle, int p) { 
    for (int i = p, j = 0; i < needle.length; ++i, ++j) { 
     if (needle[i] != needle[j]) { 
     return false; 
     } 
    } 
    return true; 
    } 

    /** 
    * Returns the maximum length of the substring ends at p and is a suffix. 
    */ 
    private static int suffixLength(char[] needle, int p) { 
    int len = 0; 
    for (int i = p, j = needle.length - 1; 
     i >= 0 && needle[i] == needle[j]; --i, --j) { 
     len += 1; 
    } 
    return len; 
    } 

Answer 2

如果有很多的關鍵詞，尤其是具有共同的前綴，一個trie可能工作得很好這裏。

我會假設你想子，不是說說而已，即給定一個關鍵字bah，它會在bahama找到bah。修改此以防止這一點應該不困難。

我還假設你沒有關鍵字，它的子串是關鍵字（即bah和bahama不能都是關鍵字）。迎合這一點也不應該太困難。

只要對字符串中的每個字符開始在樹頂部搜索並繼續搜索樹中的每個現有指針。一旦指針中的一個到達一個有效的單詞，按照你的意願做，並可能刪除樹中的所有指針。

複雜性：

O(max(n2, mn))其中m是樹中的節點的數量，在最壞的情況下，雖然平均情況下的性能應該是好了很多。

例子：

所以，讓我們說我們有關鍵字：

ab 
b 
caa 

我們可能會得到一棵樹一樣：

 o 
    /|\ 
    a/| \ c 
/|b \ 
    o o o 
    | b  | a 
    o  o 
      | a 
      o 

（o只是一個節點）

現在，對於輸入字符串caab，我們先來看看c：（x表示在樹中的指針）

 o 
    /|\ 
    a/| \ c 
/|b \ 
    o o x 
    | b  | a 
    o  o 
      | a 
      o 

注意右邊的新指針。

然後a：

 o 
    /|\ 
    a/| \ c 
/|b \ 
    x o o 
    | b  | a 
    o  x 
      | a 
      o 

注意左邊的新指針和一個在右邊先進。

然後a：

 o 
    /|\ 
    a/| \ c 
/|b \ 
    o o o 
    | b  | a 
    o  o 
      | a 
      x 

注意左邊的指針消失，右側先進的一個。

現在我們從找到一個有效的單詞後刪除右邊的那個。

然後b：

 o 
    /|\ 
    a/| \ c 
/|b \ 
    o x o 
    | b  | a 
    o  o 
      | a 
      o 

注意在中間，我們隨後也刪除，因爲我們找到了一個有效的字的新指針。