搜索关键字列表

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 

注意在中间，我们随后也删除，因为我们找到了一个有效的字的新指针。