查詢數據庫的記錄幾乎相似匹配字符串值

的情況是，我有具有地址和城市場，其中有插入值，以便多的沒有這樣的標準方式約50萬記錄一個龐大的數據庫用戶，例如一些已插入他們的城市值作爲班加羅爾和另一個已插入其城市值作爲begaluru或benglore（拼錯）查詢數據庫的記錄幾乎相似匹配字符串值

另外在地址場相同的情況下使用R 3與多個記錄已插入它的地址值，但該值是不一樣exaclty例如Mountville公園托馬斯門和Montlee公園thonas GTE。

我需要獲取所有這些都是具有相同的和幾乎相同的值記錄（不知missplelled）地址和城市的。

有沒有什麼辦法讓這些記錄幾乎相似，但無法比擬的價值？

謝謝。

來源

2012-02-22 Nishit Jain

之前，這將是一個昂貴的查詢，但因爲這將有希望成爲一個一次性操作，你可能考慮在Levenshtein distance公式中尋找。

爲了避免需要計算您的表的笛卡爾乘積的距離，您可以首先縮小一組城市和地址，以便與更快的理智檢查進行比較......例如，它們以相同的字母開頭，並且具有相似的長度。

然後，您可以只返回記錄一個非常小的Levenshtein距離，然後逐漸增加的距離，直到你開始得到太多的誤報開始。

Here's an implementation directly in MySql：

CREATE FUNCTION levenshtein(s1 VARCHAR(255), s2 VARCHAR(255)) 
    RETURNS INT 
    DETERMINISTIC 
    BEGIN 
    DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT; 
    DECLARE s1_char CHAR; 
    -- max strlen=255 
    DECLARE cv0, cv1 VARBINARY(256); 
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0; 
    IF s1 = s2 THEN 
     RETURN 0; 
    ELSEIF s1_len = 0 THEN 
     RETURN s2_len; 
    ELSEIF s2_len = 0 THEN 
     RETURN s1_len; 
    ELSE 
     WHILE j <= s2_len DO 
     SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1; 
     END WHILE; 
     WHILE i <= s1_len DO 
     SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1; 
     WHILE j <= s2_len DO 
      SET c = c + 1; 
      IF s1_char = SUBSTRING(s2, j, 1) THEN 
      SET cost = 0; ELSE SET cost = 1; 
      END IF; 
      SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost; 
      IF c > c_temp THEN SET c = c_temp; END IF; 
      SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1; 
      IF c > c_temp THEN 
       SET c = c_temp; 
      END IF; 
      SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1; 
     END WHILE; 
     SET cv1 = cv0, i = i + 1; 
     END WHILE; 
    END IF; 
    RETURN c; 
    END;

此功能可以在隨後的AA輔助函數使用如下：

CREATE FUNCTION levenshtein_ratio(s1 VARCHAR(255), s2 VARCHAR(255)) 
    RETURNS INT 
    DETERMINISTIC 
    BEGIN 
    DECLARE s1_len, s2_len, max_len INT; 
    SET s1_len = LENGTH(s1), s2_len = LENGTH(s2); 
    IF s1_len > s2_len THEN 
     SET max_len = s1_len; 
    ELSE 
     SET max_len = s2_len; 
    END IF; 
    RETURN ROUND((1 - LEVENSHTEIN(s1, s2)/max_len) * 100); 
    END;

您也可以通過傳遞在當前的最大距離優化levenshtein功能...如果該功能通過該距離，則退出而不計算準確的距離。

來源

2012-02-22 14:19:26

哎喲。這是一個棘手的問題。無論您使用何種方法，您最終都會遇到非常昂貴的查詢。我的建議是，您編寫的應用程序在通過拼寫檢查器運行數據後將數據複製到新表中。您還可以用Java實現查詢，讀取每條記錄，拼寫檢查字段並進行比較。

幸運的是，一些拼寫檢查軟件已經存在...您可以看看Jazy或JOrtho爲此目的。

來源

2012-02-22 14:00:43

SOUNDEX（）對您的使用可能有限，但是我從全球酒店名稱規範化的經驗中知道（類似問題與拋出的錯誤翻譯問題），可靠的解決方案將非常難以創建。

最好的選擇，將有涉及製作一個標準的城市和/或地址列表。我不知道是否有任何等同於英國可用的郵政編碼地址文件（http://www.royalmail.com/marketing-services/address-management-unit/address-data-products/postcode-address-file-paf）的文件適用於您所在的地區。但是，這對於規範化現有數據並不實際。

最終可用的任何選項將需要顯著人力投入，以確保任何normalisations沒有錯誤匹配。

在第一個例子中我希望依賴任何可用的區號（Google告訴我在印度這是一個PIN碼？）。最有可能的數據庫可用於將這些代碼映射到區域（http://www.geopostcodes.com/india_zip_codes），這將消除標準化更廣泛區域的問題（假設它們的PIN代碼是正確的）

關於街道標準化，您可能必須如果你想規範化拼寫錯誤/區別人們如何寫個人街名或地點，請看SOUNDEX（）或某種仲裁系統。

來源

2012-02-22 14:01:38

這取決於你所使用的語言，比如你可以刪除元音比較字符串

來源

2012-02-22 14:07:06

您可以創建一個表，並用它在搜索幫助

CREATE TABLE `correct_spelling` (
    correctString varchar(100) not null, 
    variant  varchar(100) not null, 
    primary key (correctString) 
)

您將填充表與已知變種（手動）。雖然這在短期內聽起來很瘋狂，但從長遠來看，這可能是您的最佳解決方案。它可能在以後的生活中可重用。

來源

2012-02-29 00:38:07 tribal

查詢數據庫的記錄幾乎相似匹配字符串值

回答

相關問題