瞭解字符匹配和標記匹配之間的區別

使用子字符串/字符匹配實現的搜索功能與使用基於標記的匹配實現的搜索功能之間的區別是什麼？我正在爲產品規劃目的尋找一種直觀且不太過於技術的解釋。以下是我的解釋，或多或少是正確的，但不直觀或完整。瞭解字符匹配和標記匹配之間的區別

答案與您選擇的最小匹配單位有關：您是否匹配單個字符，或者您是否匹配單個單詞？子串匹配的例子：

"lady's hat".contains("l") == true 
"lady's hat".contains("lady's hat") == true

而令牌匹配可能是這樣的：

Array("lady", "s", "hat").contains("l") == false 
Array("lady", "s", "hat").contains("lady") == true 
Array("lady", "s", "hat").contains("lady's hat") == false

顯然，這是一個過於簡單化和迴避很多問題。我想我可能會試圖在錯誤的抽象層面上解釋這個問題。

上下文：我在Java中搜索和篩選Web應用程序的功能。我們目前的方法使用LIKE操作符和MySQL，並且遭受全表掃描的明顯性能問題。我們正在考慮使用Lucene，Solr或反規範化我們的關係數據。

來源

2012-07-31 Landon Kuhn

字符匹配
字符匹配是昂貴的，並且將始終是O（NP），其中N =字符數來搜索和P =搜索術語的數目。

這是線性搜索pseduo碼：必須使用線性搜索操作來搜索

function linear_search(items, terms, match_mode) { 
    matched_items = new array(); 
    for(item_idx=0, item_count=count(items);item_idx < item_count;++item_idx) { 
     doc = items[item_idx]; 
     match_count = 0; 
     for(term_idx=0, term_count=count(terms);term_idx < term_count;++term_idx) { 
      term = terms[term_idx]; 
      for(i=0, doc_len = strlen(doc), term_len = strlen(term) ; i < doc_len; i += term_len) { 
       if(substr(doc, i, term_len) == term) { 
        if(mode == 'ANY') { 
         matched_items[]=item_idx; 
         continue 3; 
        } 
        ++match_count; 
        break; 
       } 
      } 
     } 
     if(mode == 'ALL' && (match_count == count(items)) matched_items[]=item_idx; 
    } 
    return matched_items; 
}

每個文檔（行），因此n實際上是在數據總和（strlen的（N））設置（每一行，又名一個文件是一個N）。 O（NP）對於大型文檔或許多文檔或兩者都是非常長的操作。

倒排索引（標記搜索）在另一方面
基於令牌的搜索預解析數據成標記和創建一個「倒排索引」。首先將每個文檔（要搜索的文本）分解爲術語，然後將這些術語編入索引並指向文檔。
例如，給定的原始數據：創建

1, the quick brown fox 
2, all cows eat grass 
3, all the world

反向索引：

all => 2, 3 
brown => 1 
cows => 2 
eat => 2 
fox => 1 
grass => 2 
quick => 1 
the => 1, 3 
world => 3

B-樹通常在令牌創建。因此，對令牌的查找是O（log（N））以獲取與令牌匹配的文檔列表。查詢獲取實際數據通常是另一種O（log（N））操作。
這導致反向索引操作成本計算中，假設B樹結構：

O(log(TERM_COUNT)) + O(log(DOC_MATCH_COUNT))

字位置分析
通常索引將存儲字位置在文件中，與相匹配的文檔一起。這使得定位分析，比如「富」近「酒吧」沒有諮詢文件本身：

all => 2:1, 3:1 
brown => 1:3 
cows => 2:2 
eat => 2:3 
fox => 1:4 
grass => 2:4 
quick => 1:2 
the => 1:1, 3:2 
world => 3:3

制止
此外，「制止」，如波特施特默爾（HTTP：// EN .wikipedia.org/wiki/Stemming）通常應用於索引之前和搜索之前的術語。

一個詞幹將會將'brandded'和'branding'這樣的詞轉換成'brand'，這樣一個品牌的搜索就會返回匹配品牌或品牌或品牌的文檔。

來源

2012-08-01 00:15:27

瞭解字符匹配和標記匹配之間的區別

回答

相關問題