分層字符串的頻率分佈

Question

我有大約10K這樣的分層字符串。他們可以有多達10-12層次的層次結構（/）。

/a/b/c /a/b/d /e/b/c

每個級別我，我想計算層級路徑向上分配I級。因此，對於上述情況下，這將是這樣的：

level 0: 
/a 0.67 
/e 0.33 

level 1: 
/a/b 0.67 
/e/b 0.33 

level 2: 
/a/b/c 0.33 
/a/b/d 0.33 
/e/b/c 0.33 

我怎樣纔能有效地爲這個字符串10K 10-12級的最大做。這必須是一個非常常見的字符串操作算法，但我忘記了正確的名字。謝謝。

Answer 1

創建一個按字符串名稱進行索引幷包含計數的字典（映射）。

對於每個字符串，將其拆分到路徑分隔符'/'上。然後，從一個空白字符串開始，將每個段添加到字符串中，並增加地圖中的計數。看起來像這樣：

for each path string 
    split path into segments 
    newPath = '' 
    for each segment 
     add to newpath 
     increment count of newpath occurrences in dictionary 
    end 
end 

這樣做後，你有一個子路徑和數字的列表。在你的榜樣，你必須：

a,2 
a/b,2 
a/b/c,1 
a/b/d,1 
e,1 
e/b,1 
e/c,1 

現在，所有你需要做的就是去通過地圖和劃分數由路徑字符串總數：

for each item in dictionary 
    output key, count/string_count 

在這種情況下， string_count是3，因爲這是你提供的字符串的原始數量。

如果花費超過一秒來處理最多12層級的所有10K字符串，我會感到非常驚訝。