文字處理簡介：讓我們在 Python 中快速製作字典（第 2 部分）

創建 double 陣列

雙精度陣列是如何實現 Trie 樹的？

首先，準備一個名為 「base」 的一維整數陣列。
此陣列的每個元素都表示一個節點。
基陣列的索引從 1 開始。 （不使用 0 位置）
換句話說，節點 1 是 root。 這裡有一個 1。
base[1] = 1。

在前面的示例中，headword 的首字母是 “で” 和 “ど”。
那麼，根通過 「at」 轉換到的下一個節點在哪裡？

要進行準備，請為標題的每個字母分配一個標識號。
您可以按原樣使用某些編碼的字元代碼。
由於字元數較少，因此我們在此處從 1 開始，並適當地分配字元 ID。
單詞和字母的顯示順序如下。

和: 1毫米: 2做: 3這: 4血: 5你: 6（二）: 7是的: 8

“De” 現在是 1，“Do” 現在是 3。 code['in']=1， code['ど']=3.
順便說一句，正如我稍後將解釋的那樣，字元ID的數位0是單詞的結尾（過渡到葉節點）。
由於我們討論了葉節點，我將按照單詞的出現順序為單詞分配ID。

書房:1哪裡:2砰:3東燦:4穩步:5東貝:6

現在，以這種方式，從 root 過渡到字元 「at」 的節點的位置是
它採用 root base 的值加上字元 ID。 你什麼意思：

base[1] + code['in'] = 1 + 1 = 2

它來到了。 在 「do」 的情況下執行相同的作，

base[1] + code['ど'] = 1 + 3 = 4

這將重新填充基陣列編號 2 和 4。
這樣，過渡目標的節點位置就是 「基礎值 + 字元 ID」 的值。
這有點神奇。 文字資訊已被吸收到 「過渡移動量」 中。

這裏的問題是，通過將任意字元ID值添加到base[1]的值中，
可以從 root 過渡到任何節點。
我不希望下一個字元只是“で”和“ど”，所以這是一個問題。
因此，我們將準備另一個名為 「check」 的一維整數陣列。
在 check，放入它的來源 （= 父節點的索引）。
如果父節點是 root，則為 1。 此外，根本身應設置為0。 如果你把它寫在公式中：

檢查 [1] = 0
檢查[2] = 1
檢查[4] = 1

通過這種方式，Trie 樹由兩個陣列表示，base 和 check。
這就是 「double array」 這個名字的由來。
可以將其視為「double 數位列中的節點具有位置資訊、基本元件和 check 元件」。。
這可能會很好。
讓我們看一下到目前為止的表格。

現在，節點 1、2 和 4 已填充。 3 仍為空。
數位 2 和 4 的基值仍然存在，但如何確定它們呢？

當通過字母 c 從位置 s 過渡到位置 t 時，情況如下。

t = 基數 [s] + 代碼 [c]
檢查[t] = s

如果你按照自己的喜好決定 base[s] 的值，那麼當將來節點數穩步增加時，
發生具有預先存在節點的位置擊球。
相反，這樣就不會發生這種情況，也就是說，這樣下一個節點就會過渡到一個非常空置的地方。
確定base[s] 的值。

標題： “Den”， “Where”， “Don”， “Donchan”， “Dondon”， “Donbe”， “， ”Donchan“， ”Dondon“， ”Donbe“， ”Where“， ”Don“， ”Donchan“， ”Dondon“， ”Donbe“， ”Donbe“，
例如，從「don」的第二個字母「n」開始，就是「詞尾」、「chi」、「do」、「be」
子節點有四個分支，因此我們必須確保所有分支都不會相互碰撞。
我認為您可以將基本元件稱為偏移值。
通常，您應該選擇最小化偏移值，即盡可能減少目標組合的左側。
隨著 double 陣列的增長，空間似乎從左側被填充了。

現在，讓我們一步一步地看一下 double 陣列的增長。
其實，只剩下一個更重要的概念需要解釋：葉節點處理，請放輕鬆。
即使你第一次沒有得到它，如果你一邊做筆記一邊讀幾遍，你也一定會把它記在你的腦海裡。

順便說一句，這次我們將按照單詞 ID 的順序註冊，所以
這意味著它是一個深度優先的創作。
作為替代方法，您可以先為所有 headwords 註冊從根到第一個字元的過渡，然後使用
也可以在所有詞條中註冊第一個字母→第二個字母的過渡。
在這種情況下，它將是一個廣度優先的創作。

第 1 步：“In”→“Den”

它是從過渡源 s = 2 的過渡。 字元 ID 為代碼 ['ん'] = 2。
如果 base[2] = 1，則過渡目標是 t = base[s] + code[c ] = 1 + 2 = 3。
您可以過渡到空位置（在最左側）。 將父節點位置放在該處。
檢查[3] = s = 2

現在，我用 「den」 來結束這個詞。 由於“Den...”後面沒有其他標題。
過渡沒有分支（葉節點沒有同級節點）。
通常，您可以通過將轉換目標視為code[leaf node] = 0 來創建葉節點。
如果沒有分支，就不要費心創建葉子節點，並添加
將單詞ID的符號倒置為負數。
它可以節省記憶體並略微加快搜索速度。
“den” 的單詞 ID 為 1，因此 base[3] = -1
在上表中，“de” → “den” 之間的過渡簡化為 “→”。

第 2 步：“執行”→“在哪裡”“唐”

它是從過渡源 s = 4 的過渡。
“do”、“ko”和“n”有兩個過渡目標。
code['こ'] = 4 且 code['ん'] = 2，所以如果 base[4] = 3，則
目標節點位置已明確。 讓我們來看看每個。

“Do” → “Where”
轉換為 t = base[4] + code['ko'] = 3 + 4 = 7，因此 check[7] = s = 4
我來到了“where”這個詞的結尾，但沒有分支（“where...”後面沒有其他詞頭），所以
和以前一樣，單詞 ID 2 被倒置，使得 base[4] = -2

“Do” → “Don”
轉換為 t = base[4] + code['n'] = 3 + 2 = 5，因此 check[5] = s = 4
我來到了 “don” 這個詞的結尾，但從 “don” 開始，它分支成 “chi”、“do” 和 “be”。
由於無法將單詞 ID （倒置符號） 放在base[t] 中，因此將創建一個新的葉節點。
我現在先說到這裡，下一步再考慮。

這樣，在 double 陣列中，即使你以深度優先的方式創建它，你也可以使用
有必要始終考慮連接的寬度（分支的數量）。 這有點有趣。

第 3 步：“Don” → “Don （end of word）”， “Donchi”， “Dondo”， “Donbe”

它是從過渡源 s = 5 的過渡。
代碼[end] = 0， 代碼['ち'] = 5， 代碼['ど'] = 3， 代碼['べ'] = 7。
base[5] = 6 是確定目標節點位置的好方法。
讓我們來看看每個。

單詞結尾 → “don”
這是我之前推遲的過程。
轉換為 t = base[5] + code[end] = 6，因此 check[6] = s = 5
由於它是單詞的結尾，因此“Don”的單詞 ID 的 3 的符號是倒置的。
基數[6] = -3
如果有分支，請創建一個像這樣的新葉節點，然後使用
將單詞ID（倒置符號）放在那裡是
這是與沒有分支的情況相比，處理方式的差異。

“Don” → “Donchi”
轉換到 t = base[5] + code['chi'] = 6 + 5 = 11，所以 check[11] = s = 5

“Don” → “Dondo”
轉換為 t = base[5] + code['do'] = 6 + 3 = 9，因此 check[9] = s = 5

“Don” → “Donbe”
轉換為 t = base[5] + code['be'] = 6 + 7 = 13，因此 check[13] = s = 5

第 4 步：“Donchi” → “Doncha” → “Donchan”

到目前為止，我一直在一次處理一個字母，但 “Donchi” → “Donchan” 沒有分支。
我將用兩個字母來總結解釋。

“Donchi” → “Doncha”
過渡源 s = 11。 code['ゃ'] = 6，所以如果 base[11] = 2，則轉換為 t = base[11] + code['ゃ'] = 8
所以 check[8] = 11

“Doncha” → “Donchan”
過渡源 s = 8。 code['ん'] = 2，所以如果 base[8] = 8，那麼轉換為 t = base[8] + code['ん'] = 10
所以 check[10] = 8
我已經到了這個詞的結尾，但在過渡到葉節點時也沒有分支。 由於單詞ID為4
反轉符號，使base[10] = -4

第 5 步：“Dondo” → “Donbe”、“Donbe” → “Donbe”

double 陣列是完整的。 （哦，解釋......？ 感謝您的光臨。
最後，以下是有關創建 double 陣列的一些重要資訊。

1234法典