[Algoritme] Efficient woordjes tellen

[BestTested!]

Ik zit met een probleem dat niet echt moeilijk is als het om weinig data gaat, maar aangezien het om een aantal GB gaat, moet ik een efficiente manier vinden om woorden te tellen.

Ik moet de Term Frequency van woorden vinden, dat wil zeggen, ik moet tellen hoe vaak een bepaald woord voorkomt in een bepaalde tekst.
Om dit gewoon te schrijven is niet zo moeilijk, alleen kom ik bij al mijn oplossing uit op algoritmes die niet erg efficient zijn (hoge tijd-complexiteit)

Voorbeeldje: Stel de tekst:
_{uit: Principles of Data Mining, Manilla, Hand et al.}

code:

TF stands for Term Frequency and simply means that each term component in a term vector is multiplied by the frequency by which that term occurs in the document

Ik heb een tekst in een String[], waarin elke woord een element is. Deze woorden zijn allemaal 'gecleaned' van rotzooi ASCII en gestemmed naar naar hun grondterm. Wat er dan moet uitkomen is, een gesorteerde lijst moet hoevaak elke term voorkomt:

code:

Term (4)
Frequency (2)
By (2)

Bij elke oplossing die ik verzin kom ik dus uit op een kwadratische (of slechtere) methode, maar volgens mijn gevoel moet dit ook sneller kunnen.

Ik gebruik Java hiervoor, dus heb wel een aantal handige Collections tot mijn beschikking, helaas kan een TreeMap bijvoorbeeld niet gebruikt worden omdat deze niet op Values kan sorteren en geen duplicate Keys kan bevatten. Een HashMap kan weer niet sorteren. Zelf een classe maken implements compterator, geeft problemen met het controleren of een term al bestaat, wat betekend dat je een lijst moet bijhouden en door die lijst moet lopen.

[Verwijderd]

Waarom niet een hashtable gebruiken tijdens het lezen van de tekst(en) en de elementen uit de hashtable achteraf sorteren?

[Sendy]

Je zou de woordjes + het aantal in een sorteerboom kunnen opslaan. Opzoeken in de boom is n . log(n).

[Stubby]

Verwijderd schreef op dinsdag 11 april 2006 @ 15:30:
Waarom niet een hashtable gebruiken tijdens het lezen van de tekst(en) en de elementen uit de hashtable achteraf sorteren?

Dit is idd de snelste manier, omdat het invoegen in de HASHMAP n * O(1) = O(n) is en het vervolgens sorteren van deze Collectie kost O(n log n). Sneller kan gewoon niet, als je het gesorteerd wil hebben.

[BestTested!]

Stubby schreef op dinsdag 11 april 2006 @ 15:57:
[...]
Dit is idd de snelste manier, omdat het invoegen in de HASHMAP n * O(1) = O(n) is en het vervolgens sorteren van deze Collectie kost O(n log n). Sneller kan gewoon niet, als je het gesorteerd wil hebben.

Maar dat betekend dat ik twee keer erdoorheen loop (sorteren is dan wel O(n log n)), ik was zelf meer aan het denken in de richting van de lijst gesorteed houden terwijl je dingen toevoegd.
Zoals je ziet is de kans dat je twee dezelfde woorden tegenkomt niet erg groot, zodat de complexiteit van de worst-case scenario's niet echt representatief is voor de 'in-praktijk' werking.

[Hersen-cel gekraak] Wat als ik nu een lijst (of zelfs tree) bij houd, en in dan met bubble-sort bij het toevoegen controleer of het gewijzigde element nog goed staat. [/Hersen-cel gekraak]

[TheBlasphemer]

Als je bepaalde combinaties van letters zoekt (zoals bijv woorden )
Moet je Aho-Corasick eens proberen. Je maakt dan een soort boom waardoor je traversed tijdens het lezen van de text, en dan bijhouden hoe vaak je in welke uiteinden van de boom belandt

Links:
Google
Goede powerpoint presentatie met uitleg
Wikipedia
Java voorbeeld

Is dit wat je zoekt ?

[BestTested!]

TheBlasphemer schreef op dinsdag 11 april 2006 @ 16:16:
Als je bepaalde combinaties van letters zoekt (zoals bijv woorden )
Moet je Aho-Corasick eens proberen. Je maakt dan een soort boom waardoor je traversed tijdens het lezen van de text, en dan bijhouden hoe vaak je in welke uiteinden van de boom belandt

Links:
...

Is dit wat je zoekt ?

Ook niet echt. Met AC kan ik enkel het aantal keren tellen dan een woord voorkomt, ik doe dit momenteel door String.equals(anotherString), maar ik moet nog steeds de hele lijst van woorden doorlopen en achteraf nog sorteren.

[Verwijderd]

BestTested! schreef op dinsdag 11 april 2006 @ 16:09:
[...]


Maar dat betekend dat ik twee keer erdoorheen loop (sorteren is dan wel O(n log n)), ik was zelf meer aan het denken in de richting van de lijst gesorteed houden terwijl je dingen toevoegd.
Zoals je ziet is de kans dat je twee dezelfde woorden tegenkomt niet erg groot, zodat de complexiteit van de worst-case scenario's niet echt representatief is voor de 'in-praktijk' werking.

[Hersen-cel gekraak] Wat als ik nu een lijst (of zelfs tree) bij houd, en in dan met bubble-sort bij het toevoegen controleer of het gewijzigde element nog goed staat. [/Hersen-cel gekraak]

Volgens mij maak je het jezelf onnodig lastig. Als de woorden gewoon uit een natuurlijke taal komen, dan zul je hooguit vijf- tot tienduizend verschillende woorden hebben. Het is een eitje om die achteraf te sorteren.

[Sendy]

BestTested! schreef op dinsdag 11 april 2006 @ 16:09:
[...]
Maar dat betekend dat ik twee keer erdoorheen loop (sorteren is dan wel O(n log n)), ik was zelf meer aan het denken in de richting van de lijst gesorteed houden terwijl je dingen toevoegd.
Zoals je ziet is de kans dat je twee dezelfde woorden tegenkomt niet erg groot, zodat de complexiteit van de worst-case scenario's niet echt representatief is voor de 'in-praktijk' werking.

[Hersen-cel gekraak] Wat als ik nu een lijst (of zelfs tree) bij houd, en in dan met bubble-sort bij het toevoegen controleer of het gewijzigde element nog goed staat. [/Hersen-cel gekraak]

Dat is dus precies wat ik bedoel. Maak een "binary search tree" of AVL-tree en stop daar alle woordjes in, als je een woord al kent hoef je alleen het countertje op te hogen.

Daarna is het een kwestie van van links naar rechts door de boom heenlopen en de woordjes te printen.

[BestTested!]

Sendy schreef op dinsdag 11 april 2006 @ 16:52:
[...]

Dat is dus precies wat ik bedoel. Maak een "binary search tree" of AVL-tree en stop daar alle woordjes in, als je een woord al kent hoef je alleen het countertje op te hogen.

Daarna is het een kwestie van van links naar rechts door de boom heenlopen en de woordjes te printen.

Je vorige post had me al aan het denken gezet. Ben momenteel aan het kijken naar een tree-implementatie met behulp van een PriorityQueue (deze is in Java nameleijk als tree geimplementeerd). Ik zoek door de boom om te kijken of een woord al in de boom staat. Als een woord al in de tree staat, verhoog ik een counter, anders voeg ik hem toe aan de tree.
Omdat er niet veel dubbele woorden zullen zijn, zal de tree niet vaak opnieuw gesorteerd hoeven worden.

edit:
minder warrig gemaakt

[ Voor 14% gewijzigd door BestTested! op 12-04-2006 13:23 ]

[Sendy]

De grap is dat zo'n boom helemaal nooit "opnieuw gesorteerd" moet worden. De boom is per definitie gesorteerd. Lees er eens iets over, bijvoorbeeld hier.

edit:
Dus ook niet om jouw (onleesbare) laatste opmerking.

[ Voor 23% gewijzigd door Sendy op 12-04-2006 00:12 ]

[MSalters]

Ik verbaas me erover dat het zo moeilijk lijkt (in C++ is het zelfs het standaard probleem wat je gebruikt om map<string,int> te demonstreren). Tellen is O(N) in een hashtable, sorteren of een gesorteerde collectie opbouwen is altijd O(N log N).

Een betere complexiteit is theoretisch mogelijk, als je de woorden vooraf weet. In dat geval definieer je een perfect hash, en sorteer je vantevoren. De perfect hash is O(1), dus het tellen blijft O(N) maar het sorteren hangt niet af van de frequentie. Sowieso is dat O(M) waarbij M de grootte van de dictionary is in plaats van de input text.

[reddog33hummer]

BestTested! schreef op dinsdag 11 april 2006 @ 17:10:
[...]
Je vorige post had me al aan het denken gezet. Ben momenteel aan het kijken naar een tree-implementatie met behulp van een PriorityQueue (deze is in Java nameleijk als tree geimplementeerd). Ik zoek door de boom om te kijken of een woord al in de boom staat. Als een woord al in de tree staat, verhoog ik een counter, anders voeg ik hem toe aan de tree.
Omdat er niet veel dubbele woorden zullen zijn, zal de tree niet vaak opnieuw gesorteerd hoeven worden.

edit:
minder warrig gemaakt

Ik denk dat je hem niet helemaal snapt.
Hij zecht dat je de boom zelf moet gebruiken om te tellen.

Je bouwt een boom op met je woorden met aan elke node een letter.
Omdat een pad in de boom een sequentie van letters is heb je een woord.
Dan gebruik je de uiteinden om te tellen.

Even uit de losse pols:

code:

public class Teller{
private class Node{
     public Node[] subnodes = null;
     public int times =0;
}

private Node rootNode = new Node();

  public void newWord(String word){
     int index = 0;
     Node temp = rootNode;
     while(index < word.size()){
          int nodeIndex = ((int)Char.toUpper(word.charAt(index))) - ((int) 'A'); // gebruik de letter als index
          if(temp.subnodes == null){
                temp.subnodes = new Node[26]; //elke letter in het alfabet :P

          }
          if(subnodes[nodeIndex] == null){
                 subnodes[nodeIndex] = new Node();
          }
          temp = temp.subnodes[nodeIndex]; //Ga een laagje dieper
          index++; //volgende letter
      }
      temp.times++; //Ok dit woord gezien, dus tel er 1 bij op
  }
}

Aan het eind ga je alle paden af en heb je hoe vaak een woord voor komt.

[ Voor 17% gewijzigd door reddog33hummer op 18-04-2006 12:09 . Reden: geheugen optimalisatie ]

[Soultaker]

Waarom toch al dat geklooi met eigen datastructuren, als Java gewoon een gesorteerde map (TreeMap) in z'n standaardlibrary heeft zitten?

Natuurlijk kun je een eigen boomstructuur of hashtable bouwen, maar zorg eerst maar dat je de boel werkend hebt met een bestaande datastructuur. Verder is het implementeren van een zelf-balancerende boomstructuur bepaald niet triviaal; ik zou het alleen doen als je een hele goede reden hebt waarom de standaardlibrary niet voldoet.

[reddog33hummer]

Soultaker schreef op dinsdag 18 april 2006 @ 11:38:
Waarom toch al dat geklooi met eigen datastructuren, als Java gewoon een gesorteerde map (TreeMap) in z'n standaardlibrary heeft zitten?

Natuurlijk kun je een eigen boomstructuur of hashtable bouwen, maar zorg eerst maar dat je de boel werkend hebt met een bestaande datastructuur. Verder is het implementeren van een zelf-balancerende boomstructuur bepaald niet triviaal; ik zou het alleen doen als je een hele goede reden hebt waarom de standaardlibrary niet voldoet.

Je kan die geimplementeerde boom inderdaad gebruiken om een key op te zoeken. en dan tellers bij gaan houden.

De reden dat ik alleen even een eigen boom gebruik is omdat in dit geval de boom niet gebalanceerd hoeft te zijn en balanceren tijd kost. Je wil alleen tellen hoe vaak de woorden voorbij komen.

Ik gebruik de woorden zelf als sleutel om de indexen op te hogen en dat is veeele male sneller dan eerst opzoeken van een sleutel en daar een index aan hangen. Verder zijn in mijn implementatie subwoorden inbegrepen (huffman compressie) en nemen ze daardoor minder ruimte in (de debug en debuggen overlappen in geheugengebruik terwijl in de redblacktree je alle woorden compleetuit op moet slaan.

In wat wiskunndigere termen. wanneer je een redblacktree gebruikt is opslaan en ophalen ~ log M met M het aantal woorden. Het uiteindelijke resultaat kan je dan in M er uit halen, daarna moet er gesorteerd worden op getal wat je n log n er bij opleverd (omdat de tree gesorteerd is op de sleutel).

Deze oplossing doet ophalen en opslaan in 1 keer lopen in de boom en kost dus n in de lengte van het woord welke maximaal ~28 is (langste woord in engelse taal). Het ophalen van het resultaat kost M met M het aantal woorden. Dit zou je aan het eind nog moeten sorteren en dat is n log n. Deze laatste (bij beide) zijn n als in de verschillende woorden die er zijn (dat valt mee).

Wanneer het aantal woorden klein is, is de reblack tree efficienter. Maar met meer woorden wordt de eigen implementatie sneller. Hoeveel woorden zal 2 GB zijn denk je ?

[ Voor 27% gewijzigd door reddog33hummer op 18-04-2006 12:22 ]

[reddog33hummer]

BestTested! schreef op dinsdag 11 april 2006 @ 15:25:
Ik gebruik Java hiervoor, dus heb wel een aantal handige Collections tot mijn beschikking, helaas kan een TreeMap bijvoorbeeld niet gebruikt worden omdat deze niet op Values kan sorteren en geen duplicate Keys kan bevatten. Een HashMap kan weer niet sorteren. Zelf een classe maken implements compterator, geeft problemen met het controleren of een term al bestaat, wat betekend dat je een lijst moet bijhouden en door die lijst moet lopen.

Als je de compareble interface implementeerd kan je zelf kiezen op basis waarvan gesorteerd wordt. Je kan controleren of iets bestaat door hem gewoon op te vragen. Krijg je null terug, is hij er nog niet.

code:

Eigen waarde = (Eigen)tree.get(key);
if(waarde == null){
      waarde = new Eigen();
      tree.put(key);
}
else
{
     waarde.hoogOp();
}

Hou er wel rekening mee dat je behoorlijk wat het geheugen gaat zetten. Makkelijker is het dan om een eigen lichtgewicht boom te bouwen en niet te balanceren.

[ Voor 27% gewijzigd door reddog33hummer op 18-04-2006 12:20 ]

[Soultaker]

@reddog33hummer: mijn punt was dat je beter kunt beginnen met de standaardalgoritmen en dan pas kijken wat je kunt verbeteren; dan heb je tenminste vergelijkingsmateriaal. Je kunt bijvoorbeeld al simpelweg de TreeMap en HashMap vergelijken in termen van geheugengebruik en snelheid; ik gok dat de HashMap het kleinste en snelste is, maar dan moet je daarna nog sorteren natuurlijk.

De datastructuur die jij voorstelt wordt trouwens een trie genoemd (en die zit inderdaad niet in de standaardlibrary). Look-ups zijn inderdaad efficient, maar het geheugengebruik is in jouw implementatie waarschijnlijk toch wel een stuk groter dan met de standaard map, doordat je voor élke unieke prefix een aparte Node aanmaakt en voor elke echte prefix ook een array met 26 references. Dat tikt behoorlijk aan.

(Overigens worden tries vaak verder gecomprimeerd zodat nodes met slechts één child niet expliciet gealloceerd worden; je komt dan op een PATRICIA trie uit. Om de grote lijst met references terug te dringen wordt dan vaak op bits geselecteerd in plaats van letters, maar dat vergroot het aantal references dat je moet volgen om bij de gewenste node uit te komen wel natuurlijk.)

[reddog33hummer]

Soultaker schreef op dinsdag 18 april 2006 @ 14:02:
@reddog33hummer: mijn punt was dat je beter kunt beginnen met de standaardalgoritmen en dan pas kijken wat je kunt verbeteren; dan heb je tenminste vergelijkingsmateriaal. Je kunt bijvoorbeeld al simpelweg de TreeMap en HashMap vergelijken in termen van geheugengebruik en snelheid; ik gok dat de HashMap het kleinste en snelste is, maar dan moet je daarna nog sorteren natuurlijk.

De datastructuur die jij voorstelt wordt trouwens een trie genoemd (en die zit inderdaad niet in de standaardlibrary). Look-ups zijn inderdaad efficient, maar het geheugengebruik is in jouw implementatie waarschijnlijk toch wel een stuk groter dan met de standaard map, doordat je voor élke unieke prefix een aparte Node aanmaakt en voor elke echte prefix ook een array met 26 references. Dat tikt behoorlijk aan.

(Overigens worden tries vaak verder gecomprimeerd zodat nodes met slechts één child niet expliciet gealloceerd worden; je komt dan op een PATRICIA trie uit. Om de grote lijst met references terug te dringen wordt dan vaak op bits geselecteerd in plaats van letters, maar dat vergroot het aantal references dat je moet volgen om bij de gewenste node uit te komen wel natuurlijk.)

Een Patricia trie is inderdaad compacter. Maar in de praktijk valt het op zich wel mee, omdat je veel verschillende woorden hebt en woorden in het algemeen niet zo lang zijn. Vooral omdat je hier over 2 gb invoer praat is het geheugengebruik op zich acceptabel. Vooral vergeleken met het opslaan van al de mogelijkheden.

Je zou ook gewoon i.p.v. dat array van 26 een dynamischer groeiend iets kunnen pakken. Maar de implementatie hier was meer als idee hoe zoiets er uit zal zien.

Dat je beter met de standaard zaken kan beginnen is inderdaad waar, maar het wil nog wel eens voorkomen dat op een moment dat je een bepaalde manier bedacht hebt dat je er vast in blijft zitten.
Dan zou je in het geval met een hasmap mischien lijsten gaan gebruiken als optimalisering. Terwijl voor een grotere dataset een alternatieve denkmanier efficienter zou zijn.

[ Voor 17% gewijzigd door reddog33hummer op 18-04-2006 14:29 ]