Spellfix1 虛擬表格

3. 虛擬表格詳細資訊

4. 演算法

5. 可設定的編輯距離

6. 處理不尋常且困難的拼字

7. 輔助函式

8. editdist3 函式

9. editdist3 COST 表格

10. 測試 editcost3() 函式

1. 概觀

這個 spellfix1 虛擬表格可用於在大型詞彙中搜尋近似匹配。例如，spellfix1 可用於建議拼錯字的修正。或者，它可用於 FTS4，使用可能拼錯的字詞進行全文搜尋。

spellfix1 虛擬表格的實作保存在 SQLite 原始碼樹中的雜項擴充資料夾中，特別是在檔案 ext/misc/spellfix1.c 中。spellfix1 虛擬表格未包含在 SQLite 合併中，也不是任何標準 SQLite 建置的一部分。它是一個可載入擴充。

載入 spellfix1 擴充後，可像這樣建立 spellfix1 虛擬表格的執行個體

CREATE VIRTUAL TABLE demo USING spellfix1;

「spellfix1」一詞是 spellfix 模組的名稱，必須如所示輸入。「demo」一詞是你將建立的虛擬表格的名稱，可以根據應用程式的需求進行變更。虛擬表格最初是空的。要讓虛擬表格有用，你需要用你的詞彙填入它。假設你在名為「big_vocabulary」的表格中有一個字詞清單。然後執行以下動作

INSERT INTO demo(word) SELECT word FROM big_vocabulary;

如果您打算將此虛擬表格與 FTS4 表格（用於搜尋字詞的拼字修正）一起使用，那麼您可以使用 fts4aux 表格來擷取詞彙

INSERT INTO demo(word) SELECT term FROM search_aux WHERE col='*';

您也可以為虛擬表格提供每個單字的「排名」。「排名」是對單字常見程度的估計。數字越大表示單字越常見。如果您在填入表格時省略排名，則假設排名為 1。但是，如果您有排名資訊，您可以提供，而虛擬表格將略微偏好選取較常用的字詞。若要從 fts4aux 表格「search_aux」填入排名，請執行類似下列動作

INSERT INTO demo(word,rank)
   SELECT term, documents FROM search_aux WHERE col='*';

若要查詢虛擬表格，請在 WHERE 子句中包含 MATCH 算子。例如

SELECT word FROM demo WHERE word MATCH 'kennasaw';

使用美國地名資料集（衍生自 http://geonames.usgs.gov/domestic/download_data.htm），以上的查詢會傳回 20 個結果，開頭為

kennesaw
kenosha
kenesaw
kenaga
keanak

如果您在模式的結尾加上字元「*」，則會執行前綴搜尋。例如

SELECT word FROM demo WHERE word MATCH 'kennes*';

會產生 20 個結果，開頭為

kennesaw
kennestone
kenneson
kenneys
keanes
keenes

2. 搜尋精煉

預設情況下，spellfix1 表格最多傳回 20 個結果。（如果較佳的相符項較少，它可能會傳回少於 20 個結果。）您可以透過在查詢的 WHERE 子句中加入「top=N」字詞來變更傳回列數的上限，其中 N 是新的最大值。例如，若要查看 5 個最佳相符項

SELECT word FROM demo WHERE word MATCH 'kennes*' AND top=5;

spellfix1 虛擬表格中的每個項目都與特定語言相關，由整數「langid」欄位識別。預設的 langid 為 0，而且如果沒有採取其他動作，整個詞彙都是 0 語言的一部分。但是，如果您的應用程式需要以多種語言執行，則您可以在填入表格時指定 langid 欄位，為每種語言指定不同的詞彙項目。例如

INSERT INTO demo(word,langid) SELECT word, 0 FROM en_vocabulary;
INSERT INTO demo(word,langid) SELECT word, 1 FROM de_vocabulary;
INSERT INTO demo(word,langid) SELECT word, 2 FROM fr_vocabulary;
INSERT INTO demo(word,langid) SELECT word, 3 FROM ru_vocabulary;
INSERT INTO demo(word,langid) SELECT word, 4 FROM cn_vocabulary;

在虛擬表格已填入多種語言的項目後，請在查詢的 WHERE 子句中使用「langid=N」字詞指定感興趣的語言

SELECT word FROM demo WHERE word MATCH 'hildes*' AND langid=1;

請注意，如果您沒有在 WHERE 子句中包含「langid=N」字詞，搜尋將針對語言 0（在以上的範例中為英文）。所有 spellfix1 搜尋都針對單一語言 ID。無法一次搜尋所有語言。

3. 虛擬表格詳細資料

spellfix1 虛擬表格中的每一列都有一個獨特的 rowid，包含七個欄位加上五個額外的隱藏欄位。欄位如下

rowid: 與表格中每個單字項目相關聯的唯一整數編號。這可以用作資料庫中其他表格的外來鍵。
word: 符合模式的單字文字。word 和 pattern 都可以包含 unicode 字元，並且可以混合大小寫。
rank: 這是單字的排名，如原始 INSERT 陳述中所指定。
distance: 這是從 pattern 到 word 的編輯距離或 Levenshtein 距離。
langid: 這是單字的語言識別碼。所有查詢都是針對單一語言識別碼，預設為 0。對於任何給定的查詢，此值在所有列上都是相同的。
score: 分數是排名和距離的組合。其想法是較低的分數較佳。虛擬表格嘗試找出分數最低的單字，並且預設（除非被 ORDER BY 覆寫）會依序傳回分數增加的結果。
matchlen: 在字首搜尋中，matchlen 是與字首匹配的字串中字元的數量。對於非字首搜尋，這與 length(word) 相同。
phonehash: 此欄位顯示用於限制搜尋的音標雜湊字首。對於任何給定的查詢，此欄位在每一列中都應該相同。此資訊可用於診斷目的，通常不被視為在實際應用中是有用的。
top: (隱藏) 對於任何查詢，此值在所有列中相同。它是一個整數，表示將輸出的最大列數。實際輸出的列數可能小於此數字，但絕不會大於此數字。top 的預設值為 20，但可以在每個查詢中透過在查詢的 WHERE 子句中包含「top=N」形式的項目來變更。增加範圍會讓查詢執行得更快，但會減少可能的修正。
範圍: (隱藏) 對於任何查詢，此值在所有列中相同。範圍是衡量虛擬表格搜尋相符字詞的廣度的指標。範圍值較小會導致較廣泛的搜尋。範圍通常會自動選取，並限制在 4。應用程式可以在查詢的 WHERE 子句中包含「scope=N」形式的項目來變更範圍。增加範圍會讓查詢執行得更快，但會減少可能的修正。
srchcnt: (隱藏) 對於任何查詢，此值在所有列中相同。此值是一個整數，表示使用編輯距離演算法檢查的字詞數，以找出最終顯示的最佳相符項。此值僅供診斷使用。
soundslike: (隱藏) 在插入詞彙項目時，可以將此欄位設定為與字詞發音相符的拼字。請參閱以下的「處理不尋常且困難的拼字」區段以取得詳細資料。
指令: (隱藏) 「指令」欄位的數值永遠為 NULL。不過，應用程式可以在「指令」欄位中插入特殊字串，以在 spellfix1 虛擬表格中引發特定行為。例如，在「指令」欄位中插入字串「reset」，會導致虛擬表格重新讀取其編輯距離權重（如果有）。

4. 演算法

spellfix1 虛擬表格會建立一個名為 "%_vocab" 的單一影子表格（其中 % 會被虛擬表格的名稱取代；例如：「demo_vocab」對應到「demo」虛擬表格）。影子表格包含下列欄位

id: 唯一識別碼 (INTEGER PRIMARY KEY)
rank: 單字的排名。
langid: 此條目的語言識別碼。
word: 詞彙單字的原始 UTF8 文字
k1: 轉寫成小寫 ASCII 的單字。有一個標準的表格，用於將非 ASCII 字元對應到 ASCII。範例：「æ」->「ae」、「þ」->「th」、「ß」->「ss」、「á」->「a」，... 輔助函式 spellfix1_translit(X) 會執行非 ASCII 到 ASCII 的對應。內建的 lower(X) 函式會轉換成小寫。因此：k1 = lower(spellfix1_translit(word))。如果單字已經全部是小寫 ASCII，那麼 k1 欄位會包含 NULL。這會減少 %_vocab 表格的儲存需求，並有助於 spellfix 執行得更快。因此，建議盡可能使用小寫 ASCII 詞彙來填入 spellfix 表格。
k2: 此欄位會儲存一個音標代碼，衍生自 coalesce(k1,word)。發音相似的字母會對應到同一個符號。例如，所有母音和母音群集都會變成單一符號「A」。而字母「p」、「b」、「f」和「v」都會變成「B」。所有鼻音都會表示為「N」。依此類推。對應的基礎是來自於 Soundex、Metaphone 和其他長久以來的音標配對系統中的概念。此金鑰可以由函式 spellfix1_phonehash(X) 產生。因此：k2 = spellfix1_phonehash(coalesce(k1,word))

還有一個函數用於計算模式和字詞之間的 Wagner 編輯距離或 Levenshtein 距離。此函數顯示為 spellfix1_editdist(X,Y)。編輯距離函數傳回將 X 轉換為 Y 的「成本」。某些轉換的成本高於其他轉換。例如，將一個母音轉換為另一個母音的成本相對較低，就像加倍一個常數或省略雙重常數的第二個字元一樣。其他轉換的成本較高。這個想法是，編輯距離函數會傳回相似字詞的低成本，以及相差較遠字詞的高成本。在此實作中，任何單一字元編輯（刪除、插入或替換）的最大成本為 100，某些編輯（例如轉換母音）的成本較低。

比較的分數是模式和字詞之間的編輯距離，再調整為字詞排名以 2 為底對數的結果。例如，距離為 100 但排名為 1000 的配對，其分數為 122 (= 100 - log2(1000) + 32)，而距離為 100 但排名為 1 的配對，其分數為 131 (100 - log2(1) + 32)。（注意：常數 32 會新增到每個分數，以防止編輯距離為零時分數變為負數。）這樣一來，常用字詞的成本會稍微降低，這會讓它們傾向於移到替代拼寫清單的最上方。

拼寫校正器的直接實作方式是將搜尋字詞與詞彙中的每個字詞進行比較，然後選出分數最低的 20 個字詞。但是，詞彙中通常會有數十萬或數百萬個字詞，因此這種方法不夠快。

假設要進行拼寫校正的字詞為 X。為了限制搜尋範圍，X 會使用等效於下列方式轉換為類 k2 的金鑰：

   key = spellfix1_phonehash(lower(spellfix1_translit(X)))

然後將此金鑰限制為「範圍」字元。預設範圍值為 4，但可以在 WHERE 子句中使用「範圍=N」字詞指定替代範圍。在金鑰被截斷後，會針對詞彙中每個以簡寫金鑰開頭的 k2 值的字詞執行編輯距離。

例如，假設輸入字詞為「Paskagula」。音標為「BACACALA」，然後截斷為 4 個字元「BACA」。然後在詞彙的 4980 個項目（總共 272,597 個項目）中執行編輯距離，其 k2 值以 BACA 開頭，產生「Pascagoula」作為最佳配對。

只搜尋具有相符 langid 的詞彙條目。因此，同一個表格可以包含多種語言的項目，而且只會使用所要求的語言。預設的 langid 為 0。

5. 可設定的編輯距離

內建的 Wagner 編輯距離函式具有固定的權重，可以替換為 editdist3() 編輯距離函式，具有應用程式定義的權重和對 unicode 的支援，方法是在建立虛擬表格時，為 spellfix1 模組指定「edit_cost_table=TABLENAME」參數。例如

CREATE VIRTUAL TABLE demo2 USING spellfix1(edit_cost_table=APPCOST);

editdist3() 編輯距離函式也可以在執行期間選取或取消選取，方法是將適當的字串插入虛擬表格的「command」欄位

INSERT INTO demo2(command) VALUES('edit_cost_table=APPCOST');

在上述範例中，APPCOST 表格會被查詢以找出編輯距離係數。這是因為 spellfix1 模組名稱的「edit_cost_table=」參數的存在，導致 editdist3() 被用來取代內建的編輯距離函式。如果 APPCOST 是空字串，則會使用內建的 Wagner 編輯距離函式。

編輯距離係數通常只會從 APPCOST 表格讀取一次，然後儲存在記憶體中。因此，執行期間對 APPCOST 表格的變更通常不會影響編輯距離的結果。不過，將特殊字串「reset」插入虛擬表格的「command」欄位會導致編輯距離係數從 APPCOST 表格重新讀取。因此，當 APPCOST 表格發生變更時，應用程式應該執行類似下列的 SQL 陳述式

INSERT INTO demo2(command) VALUES("reset");

6. 處理不尋常且困難的拼字

上述演算法在多數情況下都能運作良好，但仍有例外。這些例外可透過使用「soundslike」欄位在虛擬表格中建立其他項目來處理。

例如，許多源自希臘文的單字開頭字母為「ps」，但「p」不發音。例如：psalm（詩篇）、pseudonym（化名）、psoriasis（牛皮癬）、psyche（心靈）。另一個例子是，許多蘇格蘭姓氏開頭字母可以拼寫成「Mac」或「Mc」。因此，「MacKay」和「McKay」的發音相同。

對於拼字與發音不同的單字，可以透過在虛擬表格中為同一個單字建立其他項目，但在「soundslike」欄位中加入替代拼字來進行調整。例如，「psalm」的正規項目如下：

  INSERT INTO demo(word) VALUES('psalm');

為了提升將「salm」拼字更正為「psalm」的能力，請建立一個類似這樣的其他項目：

  INSERT INTO demo(word,soundslike) VALUES('psalm','salm');

只要每個項目都有不同的 soundslike 值，就可以為同一個單字建立多個項目。請注意，如果未指定 soundslike 值，則 soundslike 預設為單字本身。

以下列出一些可能需要加入其他 soundslike 項目的情況。特定項目會根據應用程式和目標語言而有所不同。

開頭字母為「ps」的單字中不發音的「p」：psalm（詩篇）、psyche（心靈）
開頭字母為「pn」的單字中不發音的「p」：pneumonia（肺炎）、pneumatic（氣動的）
開頭字母為「pt」的單字中不發音的「p」：pterodactyl（翼龍）、ptolemaic（托勒密王朝的）
開頭字母為「dj」的單字中不發音的「d」：djinn（精靈）、Djikarta（雅加達）
開頭字母為「kn」的單字中不發音的「k」：knight（騎士）、Knuthson（克努特森）
以「gn」開頭的單字中不發音的「g」：gnarly、gnome、gnat
蘇格蘭姓氏開頭的「Mac」與「Mc」
斯拉夫語單字中的「Tch」音：柴可夫斯基與柴科夫斯基
西班牙語中發音為「h」的字母「j」：LaJolla
以「wr」與「r」開頭的單字：write 與 rite
其他有問題的單字，例如「debt」、「tsetse」、「Nguyen」、「Van Nuyes」。

7. 輔助函數

實作 spellfix1 虛擬表格的原始碼模組也實作了數個 SQL 函數，這些函數可能對使用 spellfix1 的應用程式有所幫助，或是在開發使用 spellfix1 的應用程式時進行測試或診斷工作。下列為可用的輔助函數

editdist3(P,W) editdist3(P,W,L) editdist3(T)

這些常式提供直接存取 Wagner 編輯距離函數的版本，允許應用程式定義編輯操作的權重。此函數的前兩個形式將模式 P 與單字 W 進行比較，並傳回編輯距離。在第一個函數中，langid 預設為 0，而在第二個函數中，langid 由 L 參數提供。此函數的第三個形式從 T 指定的表格中重新載入編輯距離係數。

spellfix1_editdist(P,W)

此常式提供存取內建 Wagner 編輯距離函數，此函數使用預設的固定成本。傳回的值是將 W 轉換為 P 所需的編輯距離。

spellfix1_phonehash(X)

此常式建構純 ASCII 輸入字 X 的音標雜湊，並傳回該雜湊。此常式由 spellfix1 內部使用，以將影子表的 K1 欄轉換為 K2 欄。

spellfix1_scriptcode(X)

針對輸入字串 X，此常式嘗試判定該輸入的主要文字系統，並傳回該文字系統的 ISO-15924 數字碼。目前的實作了解下列文字系統

215 - 拉丁文
220 - 西里爾文
200 - 希臘文

未來版本可能會新增其他語言碼。

spellfix1_translit(X)

此常式將 Unicode 文字轉換為純 ASCII，傳回輸入文字 X 的純 ASCII 表示。這是內部用來將詞彙字轉換為影子表 K1 欄的函式。

8. editdist3 函式

editdist3 演算法是一種函式，用來計算兩個輸入字串之間的最小編輯距離（又稱 Levenshtein 距離）。editdist3 演算法是 spellfix1 預設編輯距離函式的可設定替代方案。editdist3 的功能包括

它適用於 Unicode（UTF8）文字。
應用程式可以提供插入、刪除和替換成本的表格。
可以在成本表格中列舉多個字元的插入、刪除和替換。

9. editdist3 COST 表格

若要編寫 editdist3 的成本，請建立類似下列的表格

CREATE TABLE editcost(
  iLang INT,   -- The language ID
  cFrom TEXT,  -- Convert text from this
  cTo   TEXT,  -- Convert text into this
  iCost INT    -- The cost of doing the conversion
);

成本表格可以命名為任何您想要的，不一定要稱為「editcost」。而且表格可以包含其他欄位。唯一的需求是表格必須包含上面顯示的四個欄位，且名稱完全相同。

iLang 欄位是一個非負整數，用來識別適用於特定語言的一組成本。editdist3 函式只會對任何給定的編輯距離計算使用單一 iLang 值。預設值為 0。建議只須使用單一語言的應用程式對所有項目始終使用 iLang==0。

iCost 欄位是將 cFrom 轉換成 cTo 的數值成本。此值應為非負整數，且可能小於 100。預設單一字元插入和刪除成本為 100，而預設單一字元對單一字元替換成本為 150。成本為 10000 或更高會被視為「無限大」，並導致規則被忽略。

cFrom 和 cTo 欄位顯示編輯轉換字串。任一欄位或兩欄位都可能包含多個字元。或任一欄位（但不能同時兩欄位）可能包含空字串。當 cFrom 為空時，那是插入 cTo 的成本。當 cTo 為空時，那是刪除 cFrom 的成本。

在 spellfix1 演算法中，cFrom 是使用者輸入的文字，而 cTo 是資料庫中存在的正確拼寫文字。editdist3 演算法的目標是判斷使用者輸入的文字與字典文字有多接近。

成本表中有三個特殊案例條目

cFrom	cTo	意義
''	'?'	預設插入成本
'?'	''	預設刪除成本
'?'	'?'	預設替換成本

如果省略上述顯示的任何特殊案例條目，則插入和刪除使用 100 的值，而替換使用 150 的值。若要停用預設插入、刪除和/或替換，請將其各自的成本設定為 10000 或更高。

成本表中的其他條目特定轉換特定字元。特定轉換的成本應小於預設成本，否則預設成本會優先，而特定轉換永遠不會被使用。

一些範例，成本表條目

INSERT INTO editcost(iLang, cFrom, cTo, iCost)
VALUES(0, 'a', 'ä', 5);

上述規則表示使用者輸入中的字母「a」可以與字典中的字母「ä」配對，罰則為 5。

INSERT INTO editcost(iLang, cFrom, cTo, iCost)
VALUES(0, 'ss', 'ß', 8);

cFrom 和 cTo 中字元的數量不需要相同。上述規則表示使用者輸入的「ss」將會比對「ß」，且懲罰值為 8。

10. 測試 editcost3() 函數

如果在建立 spellfix1 虛擬表格時，將「edit_cost_table=TABLE」選項指定為引數，則 spellfix1 虛擬表格會使用 editdist3。不過，也可以使用內建的「editdist3()」SQL 函數直接測試 editdist3。editdist3() SQL 函數有 3 種形式

editdist3('TABLENAME');
editdist3('string1', 'string2');
editdist3('string1', 'string2', langid);

第一種形式會從名為「TABLENAME」的表格載入編輯距離係數。任何先前的係數都會被捨棄。因此，在測試權重時，如果權重表格有變更，只要重新執行 editdist3() 的單一引數形式，就能重新載入已修改的係數。請注意，editdist3() SQL 函數使用的編輯距離權重與 spellfix1 虛擬表格使用的權重無關。

第二種和第三種形式會傳回字串「string1」和「string2」之間計算出的編輯距離。在第二種形式中，使用語言識別碼 0。語言識別碼會在第三種形式中指定。

此頁面最後修改於 2023-10-10 17:29:48 UTC