將字符串映射到維護字典順序的數字

Question

我正在尋找能夠將字符串映射到數字的算法或函數，以使得結果值對應字符串的字典順序。例如：

"book" -> 50000 
"car" -> 60000 
"card" -> 65000 
"a longer string" -> 15000 
"another long string" -> 15500 
"awesome" -> 16000 

因爲它應該是這樣的函數：F（X）= Y，因此，對於任何X1 < X2 => F（X1）< F（×2），其中x是任意字符串y是一個數字。

如果x的輸入集合是有限的，那麼我總是可以進行排序並分配正確的值，但是我正在尋找通用的用於x的無限輸入集。

Answer 1

如果你需要f映射到整數這是不可能的。

假設有這樣的地圖f。考慮串a，aa，aaa等考慮值f(a)，f(aa)，f(aaa)等。我們要求f(a) < f(aa) < f(aaa) < ...我們看到f(a_n)趨於無窮大n趨於無窮大;這裏我使用的是明顯的符號a_n是字符a重複n次。現在考慮字符串b。我們要求所有n的f(a_n) < f(b)。但是f(b)是一些有限整數，我們只是表明f(a_n)趨於無窮大。我們有矛盾。沒有這樣的地圖是可能的。

也許你可以告訴我們你需要什麼？這是相當抽象的，我們可能會提出更合適的建議。此外，一般不必擔心解決「它」。 YAGNI等等。

Answer 2

寫一個可以提供給排序功能的比較器會更好。比較器需要兩個字符串並返回-1,0或1.即使您可以創建這樣的地圖，您仍然必須對其進行排序。如果你同時需要一個「散列」和訂單，那麼保留兩個數據結構的東西 - 一個保存訂單，另一個允許快速訪問。

Answer 3

也許您正在尋找Radix Tree？

基數樹，帕特里夏線索/樹，或 暴位樹是基於所述線索一組專門 數據結構 用來存儲一組字符串。與 相反，與常規三元組相比，Patricia trie的邊緣被標記爲 ，而字符序列而不是 而不是單個字符。這些可以是字符串，比特串 ，例如整數或IP地址，或 對象的字典順序。 有時名稱基數樹和 暴位樹僅適用於 樹木存儲整數和Patricia 特里結構保留比較一般 的投入，但結構適用於所有的情況下， 同樣的方式。

LWN.net also has an article describing this data structures use in the Linux kernel。

Answer 4

作爲Jason's answer的必然結果，如果您可以將您的字符串映射到有理數，這樣的映射非常簡單。如果code(c)是字符的ASCII碼c和s[i]是字符串s在i個字符，只是總結就像如下：

result <- 0 
scale <- 1 
for i from 1 to length(s) 
    scale <- scale/26 
    index <- (1 + code(s[i]) - code('a')) 
    result <- result + index/scale 
end for 
return result 

這空字符串映射到0，和所有其他字符串有理數在0和1之間，保持字典順序。如果你有任意精度的十進制浮點數，你可以用冪乘以26代替除法的除數，並且仍然有精確的可表示的數字;與任意精度的二進制浮點數字，你可以除以32的冪。

Answer 5

你要求的是暫時中止鴿子洞原則（http://en.wikipedia.org/wiki/Pigeonhole_principle）。

琴絃是鴿子，數字是洞。 鴿子比洞更多，所以你不能把每隻鴿子放在自己的洞裏。

Answer 6

我在這裏發表了一個問題https://stackoverflow.com/questions/22798824/what-lexicographic-order-means 作爲解決方法，您可以將帶零碼的空符號附加到字符串的右側，並使用第二種情況下的擴展。但是如果你有一組有限的符號（V），那麼| V * |是eqiualent到| N | - 來自Disrete Math的事實。