構造倒排索引列表的複雜性

給定n字符串S1, S2, ..., Sn和字母集A={a_1,a_2,....,a_m}。假設每個字符串中的字母都是不同的。現在我想爲每個a_i (i=1,2...,m)創建一個倒排索引。我的倒排索引也有一些特殊的地方：A中的字母按順序排列，如果在倒排索引a_i中包含一個字符串（如S_2），則a_j (j=i+1,i+2,...,m)不需要再包含S_2。總之，每個字符串只出現在倒排列表中一次。我的問題是如何以快速有效的方式建立這樣的列表？任何時間複雜度都是有限的？例如，A={a,b,e,g}, S1={abg}, S2={bg}, S3={gae}, S4={g}。然後，我倒名單應該是：構造倒排索引列表的複雜性

a: S1,S3 
b: S2  (since S1 has appeared previously, so we don't need to include it here) 
e: 
g: S4

來源

2012-09-06 John Smith

只是想知道：是否有任何理由S4不會在索引'a'下？該指數是否應該以某種方式平衡？如果沒有，看起來只要查看每個字符串的第一個字符並將其放在該索引下就足夠了。也許我並不瞭解這個問題。 –

那是我的問題。現在修復了，謝謝！ –

不是所有的情況下，如果'S3 = {gae}' –

如果我正確理解你的問題，一個簡單的解決方案是：

for each string in n strings 
    find the "smallest" character in the string 
    put the string in the list for the character

的複雜性是成正比的字符串的總長度，乘以常數進行訂單測試。

如果有一個簡單的測試方法（例如字符按字母順序排列，全部小寫，那麼<就足夠了），簡單地比較它們;否則，我建議使用一個哈希表，每一對都是一個字符及其順序，稍後再簡單地比較它們。

來源

2012-09-06 06:51:33

構造倒排索引列表的複雜性

回答

相關問題