英語以外的其他語言的嘗試的限制和替代方法？

Question

trie數據結構通常是以英文存儲字符串的好方法。它的工作原理是構建一棵樹，每個邊都用一個字母標記，並且樹中標記節點的路徑指出數據結構中的一個單詞。

這個數據結構在英語中運行良好，因爲英文字母中只有26個字母（「合理的」分支因子），這些字符具有連續的ASCII值（因此子指針可以存儲在數組鍵入的通過每個孩子使用的字母的索引），並且有許多英文單詞具有共同的前綴（所以在結構中有很多冗餘）。

我是一位母語爲英語的人，其他語言和字母的知識水平有限，但其中許多屬性似乎並不適用於其他語言。例如，我知道法語，西班牙語，德語和匈牙利語經常使用不與Unicode空間中的其餘字母連續存儲的重音字符。希伯來語和阿拉伯語的元音標記通常在每個字母的上方或下方標出。中文使用的是一個語標系統，韓文韓文字符由三個小字符組合而成。

對於以這些語言和字母存儲的數據，Do嘗試仍然有效嗎？對這類數據使用try有必要進行哪些更改（如果有的話）？是否有任何數據結構對那些特別適合他們的語言和字母的字符串起作用，但在英語中不會有用或有效？

Answer 1

作爲@ JimMischel答案的附錄，我想提出一個問題，即在其他語言中，通常有多種等效的方法來編寫相同的東西。 Vietnamese（基於拉丁/英文腳本）是一個特別好的例子，其中帶有兩種口音的字母很常見。例如，Ặ（U + 1EB6）也可以用Ă+ dot，Ạ+

Unicode normalization可以通過將字符串轉換爲標準規範的順序來解決此問題。有4種不同的變體，NFC，NFKC，NFD和NFKD。在這裏我不會詳細討論，但前兩個是「組合形式」，它傾向於縮短字符串，將基本字符與它的口音分組，而最後兩個是「分解形式」，相反。

Hangul是一個有趣的例子：它是一個字母表，雖然音節的所有字母都被拼在一起。單個字母和音節塊都以Unicode存在。規範化可以解決這個問題，儘管不同音節的數量非常大。使用NFC/NFKC對於一個trie可能沒有用處，但在這種情況下，使用NFD/NFKD將音節分解爲組成字母將會起作用。

其他一些無關的點考慮：

• 除了已經長大了加爾鬆/ GARCON點，你有棚/科特/科特迪瓦/的Côté的問題，這是完全不同的法語單詞。同樣，希伯來語和阿拉伯語的元音標記通常不是強制性的，偶爾會造成歧義。
• 英文字母與英文相比可以獲得較大的尺寸，大致是其兩倍。

---

1. 他們嚴格稱爲abugidas，在元音被寫爲變音符號/口音，但這種區別通常可以從編程的角度來看忽略。

Answer 2

我發現這種嘗試適用於西歐語言，以及西里爾文和其他許多字母語言。想想看，我遇到的唯一語言是中文，日文和其他字跡書寫系統。而對於那些人來說，這個線索毫無用處。

英文字符的順序Unicode值並不是真正的好處。雖然它暗示了簡單的節點實現：

CharNode 
    char 
    array[26] of CharNode 

該結構不是特別有用。它可以讓事情變得更快，但成本相當高。即使在特里的第二級，該陣列也非常稀疏。到達第四或第五層時，幾乎全是死角。我曾經對此進行過分析。我會環顧四周，看看我是否還有這些數字。

我發現它幾乎與節點中的可變長度數組一樣快，項目按頻率排序。除了特里的第二或第三級別之外，我所尋找的角色幾乎總是處於陣列的第一或第二位置。節省的空間相當大。每個節點（在我的實現中有104個字節）不是每個節點26個引用，而是每個引用有一個字節的計數，然後是五個字節。因此，只要特定節點（大部分時間）的孩子少於21個，我就節省了空間。運行時間很短，但在我的應用程序中不夠重要。

這是我必須對我的trie結構進行的唯一修改，以使其支持所有我正在使用的字母語言。正如我所說的，我主要用西歐語言工作，對於那些工作很好的人。我知道它確實與希伯來語和阿拉伯語一起工作，但我不知道以及它的工作原理。它符合我們的目的，但它是否會滿足母語人士是未知的。

爲了我們的目的，使用任何適合Unicode基本多語言平面的語言，我建立的trie工作得非常好。與代理對一起工作時有點不可思議，但我們幾乎忽視了這些。基本上，我們只是將代理對作爲兩個角色來處理，然後讓它繼續。

您必須決定是否要將重音字符視爲單獨的字符，還是要映射它們。例如，考慮一些人會拼寫「garcon」的法語單詞「garçon」，要麼是因爲他們不瞭解任何更好的內容，或者他們不知道如何製作角色「ç」。根據您使用的trie的不同，您可能會發現將重音字符轉換爲不重音的等效字符很有用。但我想這更像是一個輸入清理問題，而不是一個線程問題。

這是我相當冗長的說法，即標準的trie應該適用於任何字母語言，無需進行任何語言特定的修改。我沒有看到任何顯而易見的方法來使用字典編碼語言。我對韓國的韓文一無所知，所以我不能說一個線索是否會在那裏有用。