在C中匹配（幾個）字符串的最有效方法？

Question

我們的系統需要接受來自終端的用戶輸入並且匹配幾個已知的關鍵字字符串（可能是10）。

我們沒有空間/化合物來做正則表達式等等，代碼需要很小&快。

現在，討厭的方式做到這一點是：

// str is null-terminated, assume we know it's safe/sane here 
    if(!strncmp(str,"hello",5) 
    { 
     do_hello(); 
    } 
    else if(!strncmp(str,"world",5) 
    { 
     do_world(); 
    } 
    else 
    { 
     meh(); // Wasn't a match 
    } 

所以，有點谷歌上搜索&讀的，我深信，一個更好的辦法是預先計算各種比賽的哈希後作爲一個int，然後只用一個case語句：

// Assume hash() stops at NULL 
switch(hash(str)) 
{ 
    case HASH_OF_HELLO: 
     do_hello(); 
     break; 

    case HASH_OF_WORLD: 
     do_world(); 
     break; 

    default: 
     meh(); 
     break; 
} 

我們可以計算出* HASH_OF_match *在編譯時。這看起來似乎是從相對較小的集合中選擇字符串的更快/更優雅的方式。

所以 - 這看起來是否合理？ /這樣做有沒有明顯的問題？ /任何人都有一個更優雅的方式來做到這一點？

作爲一個腳註，這是我今天下午看到的最好看的哈希算法;），記入丹伯恩斯坦，它看起來就在眼前的工作。

unsigned int 
get_hash(const char* s) 
{ 
    unsigned int hash = 0; 
    int c; 

    while((c = *s++)) 
    { 
     // hash = hash * 33^c 
     hash = ((hash << 5) + hash)^c; 
    } 

    return hash; 
} 

Answer 1

散列問題在於用戶輸入的任意字符串可能會生成與您的匹配項，你會執行錯誤的東西。對於一個小到10的搜索，我只能堅持if-else的方法。或者使用字符串數組和函數指針數組（假定所有函數都具有相同的簽名）來選擇要執行的函數。

char const *matches[10] = {"first", "second", ..., "tenth"}; 
void (*fn[10])(void) = {&do_first, &do_second, ..., &do_tenth}; 

for(i = 0; i < 10; ++i) { 
    if(strcmp(str, matches[i]) == 0) { 
    (*fn[i])(); 
    } 
} 

Answer 2

怎麼樣只是使用嵌套switch語句的最後一個字符作爲Boyer-Moore字符串搜索算法

http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

Answer 3

也許一個解決辦法是這樣的：

struct keyword { 
    unsigned int hash; 
    const char *str; 
    void (*job)(); 
}; 

//A table with our keywords with their corresponding hashes. If you could not 
//compute the hash at compile time, a simple init() function at the beginning 
//of your program could initialize each entry by using the value in 'str' 
//You could also implement a dynamic version of this table (linked list of keywords) 
//for extending your keyword table during runtime 
struct keyword mykeywords[] = { 
    {.hash = HASH_OF_HELLO, .str = "hello", .job = do_hello}, 
    {.hash = HASH_OF_WORLD, .str = "world", .job = do_world}, 
    ... 
    {.str = 0} //signal end of list of keywords 

}; 

void run(const char *cmd) 
{ 
    unsigned int cmdhash = get_hash(cmd); 
    struct keyword *kw = mykeywords; 
    while(kw->str) { 
     //If hash matches then compare the string, since we should consider hashing collisions too! 
     //The order of conditions below is important 
     if (kw->hash == cmdhash && !strcmp(cmd, kw->str)) { 
      kw->job(); 
      break; 
     } 
     kw++; 
    } 
} 

Answer 4

聽起來像要使用gperf。

Answer 5

散列和散列表適用於大量數據。由於輸入串的數量是已知的，有限的，你也許可以考慮這個方法：

讓我們假設已知字符串

const char* STR_TABLE [STR_N] = 
{ 
    "hello", 
    "world", 
    "this", 
    "is", 
    "a", 
    "number", 
    "of", 
    "ten", 
    "test", 
    "strings" 
}; 

然後我們就可以按字母順序手動排序，在編譯之前，因爲排序表提供了更快的搜索可能性。然後您可以使用二進制搜索。

#include <stdio.h> 
#include <stdlib.h> 

#define STR_N 10 


const char* STR_TABLE [STR_N] = 
{ 
    "a", 
    "hello", 
    "is", 
    "number", 
    "of", 
    "strings", 
    "ten", 
    "test", 
    "this", 
    "world" 
}; 


int ptr_strcmp (const void* str1, const void* str2) 
{ 
    return strcmp(str1, *(const char**)str2); 
} 

int main() 
{ 
    const char* user_input = "world"; // worst case 
    const char** result; 

    result = bsearch (user_input, 
        STR_TABLE, 
        STR_N, 
        sizeof(const char*), 
        ptr_strcmp); 

    if(result != NULL) 
    { 
    printf("%s\n", *result); 
    } 
    else 
    { 
    printf("meh\n"); 
    } 

} 

這將歸結爲：

比較 「世界」 與 「中」，1個比 'W'= 'O'！。

比較「世界」與「測試」，1比較'w'！='t'。

將「world」與「this」進行比較，比較'w'！='t'。

比較「世界」和「世界」，5比較。

比較總數是8

當然還有參與這一一些開銷代碼，針對「\ 0」和二進制搜索調用檢查。您必須在您的特定平臺上測量建議的各種方法，以找出最佳方法。