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

雙精度陣列的 Python 實現（第 3 部分）

到目前為止，我們主要講了 double 陣列的創建。
如果你讀過它，你可能在某種程度上有搜索的形象。
如果創建的故事還是有點困難，請再閱讀一遍 「創建 double array」。。
嘗試移動你的手，並用雙精度數位填充表格。

以下是我想寫的關於增量搜索的內容。
在解釋的 6 個字中，在搜索 「donchan」 的同時，當你從頭到第二個字母 「don」 時，你可以找到葉子節點。
在關聯陣列（如 Pyrthon's dict）中，“donchan” 和 “don” 是單獨的搜索。
在包含 double 陣列的 Trie 樹中，它還可以同時選取搜索鍵和正向匹配子字串之間的匹配項。
特裡是樹最大的力量。

當您考慮一個查找與句子中的 headword 匹配的所有字串的過程時，
如果你要使用 dict 創建類似的字典搜索，它將從句子中的每個字元位置開始
您需要創建所有長度的子字串，並查詢每個子字串的 dict。
刑期越長，看起來就越難。
另一方面，如果您想按 Trie 樹搜索怎麼辦？
你只需要給出每個字元在句子中的位置。
您不必費心創建從該位置開始包含各種長度字串的搜索鍵。
此外，如果您無法再在 Trie 樹中過渡，您將立即退出該過程。
它甚至沒有像 dict 那樣使用長而無用的key進行搜索。
然後，當您完成一個過程時，您將獲得到目前為止子字串中與字典匹配的所有 headwords。

現在，我將嘗試編寫一個程式，該程式使用獨立於創建它的程式的雙精度陣列。
在這種情況下，jupyter-notebook 很容易，因為你可以將其移動到底部儲存格。

在創建雙精度陣列的程式中，出現了各種數量（變數）。
但是，當使用 double 陣列時，您需要：
它只是給定節點位置的base和 check 值。
您甚至不需要費心使用base陣列或 check 來獲取值。
讓我們讀取檔並直接訪問其二進位檔。

在使用的程式中，創建一個類。 DArray 類有四種方法。

方法：__init__
它讀取三個字典檔並將它們保留為成員。
但是，字元 = >字元 ID 的對應關係保存在名為 c2code 的字典中。

方法：鹼
它是一個類似 getter 的方法，從節點位置返回其base元件。

方法：檢查
它是一個類似 getter 的方法，從節點位置返回其 check 元件。

方法：search_gen
對 double 陣列的搜索與創建時節點之間的過渡完全相同。
不同之處在於沒有新的節點創建，當無法轉換時，搜索將按原樣完成。
在某種程度上，它是一種比創建 double 陣列更簡單的演算法。
此方法是生成器，因為它更容易編寫。
調用時，將其轉換為 list 或將其寫入 for 語句。

該方法輸入是執行增量搜尋的搜尋鍵（例如，一個完整的句子）
和角色ID清單。 此外，我將嘗試編寫類似偽代碼的句子。

DArray 類的程式如下所示： 它很短。

[代碼示例 4]

雙精度陣列的 Python 實現（第 4 部分）

現在，讓我們實際使用上面的 DArray 類。
我想搜索一篇較長的維琪百科文章，看看維琪百科的標題字串獲得了多少次點擊。
維琪百科禁止抓取，所以快點
從瀏覽器的文章清單中打開任何文章，複製並粘貼，然後將其另存為文本檔。

“長頁（維琪百科）”
https://ja.wikipedia.org/wiki/ Special： 長頁

我選擇了《歐洲政教分離史》（The History of the Separation of Church and State in Europe）並保存為church.txt。
它不到 500 KB，對於一篇文章來說，這是相當長的文本。

搜索文章的過程分為三個步驟：
（1） 閱讀檔的行，
（2） 從該行的字串的每個字元位置開始創建一個子字串，
（3） 對每個子字串執行增量搜索。

既然我們用 generator 編寫了 search 方法，那麼讓我們在這裡也讓每個階段都成為一個 generator。
多級生成器只是將結果作為變數一個接一個地傳遞。
通過時，不執行實際計算（惰性計算）

假設你希望上游生成器將兩個變數放在一起，並以 Tuples 的形式流它們。
如何在下游產生器中使用其中的一些？
如果在下游產生器中，

如果是這種情況，多次調用 upstream generator 的所有結果都將擴展為一個陣列。
（太可怕了！ ）
然後它嘗試將該陣列傳遞給一個雙元素元組，這會導致元素計數錯誤。

因此，如何使其工作是在下游產生器中創建一個 for 迴圈 once，
其中，您應該嘗試接收：

實際查看該程式可能會更快。

[代碼示例 5] 和 [示例結果 5]

文章中大約有85,000個字串與詞典匹配。
記憶體使用量約為 64 MB，在 Core i7 上約為 2 秒。
當我對一個關聯陣列的 dict 做同樣的事情時，它大約需要 20 秒。
在 dict 版本中，從 words.txt 創建 dict 所需的時間被排除在障礙之外。
最初，Trie 樹是一種高速演算法，但 double 陣列特別快。
（↑ 這是本文這一行的摘要）

最後的幾點思考

考慮改進此計劃所面臨的挑戰。
“如果你要把它整合到你的系統中，你不需要更多的錯誤檢查嗎？”
還有一個故事，但我現在先不說那一面。

“用 C++ 重寫”
“處理 UTF8 位元組而不是字元單位，並按原樣使用字元代碼值”
兩者都不難，所以如果您有興趣，請試一試。

“派特裡夏要成為一棵樹”
派特裡夏樹（radix trie / compact前綴樹）是Trie樹的獨創性之一。
在本文的描述和實現中，我們在 transition 不分支時壓縮了 leaf 節點。

在 Patricia 樹中，所有節點都被壓縮，而不管葉節點如何，因此沒有分支和單個路徑。
例如，在用於解釋的六個詞的世界里，“→ →詞尾”的過渡沒有分支，是一條筆直的路徑，因此可以合二為一。
然後，您將需要 9 個節點。 請數一數。

長期以來，派翠夏木一直被用作壓縮特裡木的方法。
也許吧，但它似乎也是 double 陣列中的一種常見方法。
但是，當雙重排列是 Patricia 木材時，就有很大的不同。
也就是說，由於將單個路徑放在一起，“每個節點都有多個過渡目標”。
這意味著很難從左側整齊地填充 double 陣列的空白。

創建 double 陣列時，無法並行處理多個方面。
由於它必須一次一步地連續處理，因此將其作為填充問題來解決會花費太多時間。
另一方面，如果每次創建節點時都從最左側的根位置尋找空閑空間，則該過程會逐漸變慢。
這就是為什麼“一旦空間填滿到一定程度，我們就不會在那個區域更加努力。
這似乎是一種現實的方法。 即使某個地區的所有空缺都沒有填補，在某個時間或某些條件下，
左端（您開始尋找過渡目標候選項的位置）將向右移動。

其實，在為本文創建程式時，隨著 double 陣列的增長
我們在研究自由空間會發生什麼變化的同時繼續進行這項工作。
因此，在處理過程中會發生大量沒有分支的過渡。
事實證明，這些節點從左側填充了越來越多的空白。
因此，雙精度陣列的創建也非常流暢和快速。
根據任務（或輸入數據），例如「當分支過渡在工作力中佔主導地位時」，
本文更新空位的方式可能存在問題。

出於這個原因，我在本文中沒有涉及 Patricia 樹。
如果有機會，我想再參加一次。

到目前為止，我用 Python 製作了一個字典查找程式。 感謝您的閱讀。

* 請自由安排使用本文中的程式。
但是，對於由此類劣勢造成的任何劣勢，我們概不負責。

1234法典