分层字符串的频率分布

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字符串，我会感到非常惊讶。