Häufigkeitsverteilung von hierarchischen Strings

Question

Ich habe etwa 10K hierarchische Strings wie folgt. Sie können bis zu 10-12 Hierarchieebenen (/) haben.

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

Für jede Stufe i, würde Ich mag die Verteilung des Hierarchiepfades zum Level i berechnen. Also für den obigen Fall, es so sein würde:

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 

Wie kann ich für 10K-Strings mit max von 10-12 Ebenen dies effizient zu tun. Dies muss ein sehr gewöhnlicher String-Manipulationsalgorithmus sein, aber ich vergesse den korrekten Namen. Vielen Dank.

Answer 1

Erstellen Sie ein Wörterbuch (Karte), das nach Zeichenfolgenname indiziert ist und eine Anzahl enthält.

Für jede Zeichenfolge, teilen Sie es auf dem Pfadtrennzeichen '/'. Beginnen Sie dann mit einer leeren Zeichenfolge, fügen Sie jedes Segment zur Zeichenfolge hinzu und erhöhen Sie die Anzahl in der Karte. Sieht wie folgt aus:

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

Wenn das erledigt ist, können Sie eine Liste von Unterpfaden und Zahlen haben. In Ihrem Beispiel, würden Sie haben:

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

Alles was Sie jetzt tun müssen, ist durch die Karte gehen und die Zählung durch die Gesamtzahl der Pfadzeichenfolgen unterteilen:

for each item in dictionary 
    output key, count/string_count 

In diesem Fall string_count ist 3, da dies die ursprüngliche Anzahl der von Ihnen angegebenen Strings war.

Ich wäre wirklich überrascht, wenn es mehr als eine Sekunde dauern würde, um alle 10K-Strings mit höchstens 12 Hierarchieebenen zu verarbeiten.