PHP/mysql數組搜索算法

Question

我想能夠使用PHP搜索特定字符串的數組（或更好的是，一個MySQL表的列）。但是，我的目標是返回找到的字符串和匹配字符的數量（按照正確的順序）或其他方式來查看搜索結果的合理性，然後我可以利用該信息來決定是否我想默認顯示最佳結果，或者給出用戶選項的前幾名。 我知道我可以做這樣的事情

$citysearch = mysql_query(" SELECT city FROM $table WHERE city LIKE '$city' "); 

，但我不能想出一個辦法，以確定它是如何準確。

目標將是：
a）如果搜索詞是「milwakee」或類似的詞，找到「Milwaukee」。
b）如果搜索詞是「west」，則返回「West Bend」和「Westmont」等詞。

任何人都知道一個很好的方法來做到這一點？

Answer 1

更多搜索導致我Levenshtein距離，然後similar_text，這被證明是做到這一點的最好辦法。

similar_text("input string", "match against this", $pct_accuracy); 

比較字符串，然後將精度保存爲變量。 Levenshtein距離決定了從一個字符串到另一個字符需要做多少個刪除，插入或替換單個字符的函數，並允許以不同的方式加權每個函數（例如，您可以花費更多的代價來替換一個字符而不是刪除一個字符）。它顯然更快，但不如similar_text準確。我在別處讀過的其他帖子也提到，對於少於10000個字符的字符串，速度沒有功能差異。

我最終使用的東西修改後的版本，我發現，使其工作。這最終將保存前3名的結果（除非是完全匹配）。

$input = $_POST["searchcity"]; 
$accuracy = 0; 
$runner1acc = 0; 
$runner2acc = 0; 
while ($cityarr = mysql_fetch_row($allcities)) { 
    $cityname = $cityarr[1]; 
    $cityid = $cityarr[0]; 
    $city = strtolower($cityname); 
    $diff = similar_text($input, $city, $tempacc); 

    // check for an exact match 
    if ($tempacc == '100') { 

    // closest word is this one (exact match) 
    $closest = $cityname; 
    $closestid = $cityid; 
    $accuracy = 100; 

    break; 
    } 

    if ($tempacc >= $accuracy) { // more accurate than current leader 
    $runner2 = $runner1; 
    $runner2id = $runner1id; 
    $runner2acc = $runner1acc; 
    $runner1 = $closest; 
    $runner1id = $closestid; 
    $runner1acc = $accuracy; 
    $closest = $cityname; 
    $closestid = $cityid; 
    $accuracy = $tempacc; 
    } 
    if (($tempacc < $accuracy)&&($tempacc >= $runner1acc)) { // new 2nd place 
    $runner2 = $runner1; 
    $runner2id = $runner1id; 
    $runner2acc = $runner1acc; 
    $runner1 = $cityname; 
    $runner1id = $cityid; 
    $runner1acc = $tempacc; 
    } 
    if (($tempacc < $runner1acc)&&($tempacc >= $runner2acc)) { // new 3rd place 
    $runner2 = $cityname; 
    $runner2id = $cityid; 
    $runner2acc = $tempacc; 
    } 
} 

echo "Input word: $input\n<BR>"; 
if ($accuracy == 100) { 
    echo "Exact match found: $closestid $closest\n"; 
} elseif ($accuracy > 70) { // for high accuracies, assumes that it's correct 
    echo "We think you meant $closestid $closest ($accuracy)\n"; 
} else { 
    echo "Did you mean:<BR>"; 
    echo "$closestid $closest? ($accuracy)<BR>\n"; 
    echo "$runner1id $runner1 ($runner1acc)<BR>\n"; 
    echo "$runner2id $runner2 ($runner2acc)<BR>\n"; 
} 

Answer 2

這可能非常複雜，雖然我確信它們存在，但我並沒有親自意識到任何優秀的第三方庫。不過，其他人可能會提出一些罐裝解決方案。

我在過去幾次從頭開始寫過類似的東西。如果你沿着這條路線走下去，這可能不是你想用PHP自己做的事情，因爲每個查詢都會涉及獲取所有記錄並對它們執行計算。它幾乎肯定會涉及創建一組符合您的規格的索引表。例如，你必須想出規則來描述你如何想象「密爾沃基」最終會拼寫成「milwakee」。我的解決方案是做元音壓縮和重複壓縮（不確定這些實際上是否是搜索項）。因此，雄鹿將被收錄爲：

• 密爾沃基
• m_lw__k__
• m_lw_k_

當搜索查詢進來的「密爾沃基」，我會跑在文字輸入相同的過程，然後在索引表上運行搜索：

SELECT cityId, 
     COUNT(*) 
    FROM myCityIndexTable 
WHERE term IN ('milwaukee', 'm_lw__k__', 'm_lw_k_') 

當搜索查詢輸入「milwakee」時，我w烏爾德運行上的文字輸入相同的過程，然後索引表上運行一個搜索：

SELECT cityId, 
     COUNT(*) 
    FROM myCityIndexTable 
WHERE term IN ('milwaukee', 'm_lw_k__', 'm_lw_k_') 

在密爾沃基（正確拼寫）的情況下，它會返回「3」爲計數。

對於Milwakee（拼寫錯誤），它會返回「2」的計數（因爲它不會匹配m_lw__k__模式，因爲它只有一個元音在中間）。

如果您根據計數對結果進行排序，您最終會遇到您的規則之一，那麼「密爾沃基」最終會被排序爲比「Milwakee」可能的匹配更高。

如果您想以通用方式構建此係統（如在查詢中使用$table暗示的那樣），那麼您可能需要另一個映射表以將映射表映射到適當的表。

我並不是說這是最好的（甚至是一個很好的）的方式來進行此事，只是我已經在過去做了，如果你打算嘗試做這沒有可能被證明對你有用第三方解決方案。

Answer 3

你應該在MySQL退房full text searching。還請查看Zend的Apache Lucene項目端口Zend_Search_Lucene。

Answer 4

LIKE最令人發狂的結果是這一個「％man」這將返回文件中的所有女人！ 在上市的情況下或許一個不錯的解決方案是繼續縮短搜索針。在你的情況下，當你的搜索$和「milwa」一樣短時，就會出現一個匹配。