[發明專利]數據的搜索和匹配

有效

• 申請號: 201310044062.8
• 申請日: 2013-02-04
• 公開（公告）號: CN103970798B
• 公開（公告）日: 2019-05-28
• 發明（設計）人: 黃欣榮
• 申請（專利權）人: 商業對象軟件有限公司
• 主分類號: G06F16/332
• 分類號: G06F16/332;G06F17/28;G06F17/22
• 代理公司: 北京市柳沈律師事務所 11105
• 代理人: 劉虹

此處描述一種用于便利數據的搜索和匹配的技術。根據一個實施方式，提取第一特征集和第二特征集。第一特征集與包括一個或多個第一表意元素的輸入數據串相關聯，而第二特征集與包括一個或多個第二表意元素的候選串相關聯。基于第一特征集和第二特征集來確定候選串的匹配分數。

技術領域

本公開一般涉及數據的搜索和匹配。

背景技術

搜索和匹配技術提供從數據庫中檢索數據的有用的方式。模糊串匹配(非精確或近似的串匹配)是找出與圖樣(pattern)近似匹配而不是精確匹配的串(或數據)的技術。模糊匹配的一個示例性應用是擴寬給定輸入的搜索結果的范圍。另一個示例性應用是對數據進行清洗并且標準化以提高其質量。例如，由于用戶輸入錯誤所以數據庫中的一些數據可能是不正確的。錯誤的一般來源包括錄入了與想要的數據“外形相似（look-like）”或“發音相似（sound-like）”的串。可以通過從與不正確的輸入數據近似匹配的參考域（referenceuniverse）中檢索候選記錄來糾正這樣的輸入數據，并且在將不正確的輸入數據存儲在數據庫中之前利用匹配的候選數據來替換不正確的輸入數據。

一種模糊匹配技術是首先由Robert C.Russell和Margaret K.Odell在1918和1922年開發的Soundex算法。參見美國專利第1,261,167號和第1,435,663號，其通過引用包含于此。Soundex算法通過將同音字編碼為相同的表示或關鍵字（key）而按照如英語中的發音的發聲來索引數據，以使得盡管數據在拼寫方面有微小差別也可以使它們匹配。為了比較兩個給定串，可以確定Levenshtein距離(或編輯距離)。Levenshtein距離通過計算修改一個串以獲得另一個串所需的編輯操作的最小數目來度量兩個串之間的差別。然而，常規算法的問題是它們不太適合于諸如中文或日文字符的表意（ideographic）或非英語字符。常規語音算法中使用的語音規則被設計用于英語發音，而不是用于其他語言的發音。此外，傳統的語音算法不考慮按照不同的方言組的可能的不同發音。更進一步的，計算Levenshtein距離的成本（cost）大約與兩個串長度的乘積成比例，這使得其對于長串或大數據集來說是不切實際。

因此，存在對用于搜索和匹配表意和非英語字符的新的和創新的解決方案的需要。

發明內容

此處描述一種用于便于數據的搜索和匹配的計算機實現的技術。根據一個方面，提取第一特征集和第二特征集。第一特征集與包括一個或多個第一表意元素（ideographicelement）的輸入數據串相關聯，而第二特征集與包括一個或多個第二表意元素的候選串相關聯。基于第一特征集和第二特征集來確定候選串的匹配分數。

根據本發明的另一方面，接收包括一個或多個第一表意元素的輸入數據串。此外，接收包括一個或多個第二表意元素的候選串。提取與輸入數據串相關聯的第一特征集以及與候選串相關聯的第二特征集。第一特征集和第二特征集包括語音特征和形狀特征的n元（n-gram）。基于第一特征集和第二特征集確定候選串的匹配分數。

利用將在下文中變得清楚的這些和其它優點與特征，通過參照以下詳細描述和所附權利要求與附圖，可以獲得進一步的信息。

附圖說明

在附圖中示出一些實施例，在附圖中相同的參考標號標明相同的部分，其中：

圖1是示出示范性系統的框圖；

圖2是示出示范性搜索和匹配架構的框圖；

圖3a示出語言文本到語音拼寫（phonetic spelling）的示范性轉換；

圖3b示出語言文本到基于拉丁語的部首（radical）串的示范性轉換；

圖3c示出語言文本到基于拉丁語的筆劃(stroke)串的示范性轉換；

圖4a示出示范性參考數據庫的一部分；