[ALG] T9 Boom structuur opslaan in bestand of executable

[hemaworst]

He hallo,

Ik heb tijden geleden een T9(input systeem voor phones,sms) kloon gemaakt voor de pocketpc.
Zoals je weet werkt dat zo:
met de cijfers 2 tm 8 kan je woorden maken.
code 42556 staat voor het woord hallo.

nu heb ik dus de volgende boom datastructuur gemaakt die opgebouwd is uit de volgende soorten nodes.

code:

     treenode
          m_key2 (wijst naar andere treenode)
          m_key3 (wijst naar andere treenode)
          m_key4 (wijst naar andere treenode)
           ...
          m_key9    (wijst naar andere treenode)
          m_woorden (wijst naar een linked list met woorden)

Neem het voorbeeld "Hallo"
Dit heeft code 42556.
stel ik krijg deze code in mijn programma te verwerken dan doet het programma dit:
1: currentNode=Tree.rootnode
2: currentNode=currentNode.m_4
3: currentNode=currentNode.m_2
4: currentNode=currentNode.m_5
5: currentNode=currentNode.m_5
6: currentNode=currentNode.m_6
7: Lees(traverse) alle woorden in linked lijst m_woorden en toon deze op scherm

Goed, ik hoop dat de werking duidelijk is.
Nu heb ik dit dus op mijn pocketpc werkend.
Alleen het is takke lanzaam!

Helaas moet ik nu op de pocketpc een textbestand inlezen met 130.000 woorden.
Per woord kijk ik wat de T9 code is en moet ik de tree opbouwen/aanvullen
Dit duurt dus wel een tijd, zo;n 5 minuten Dat is natuurlijk veel te langzaam)

Nu wil ik dus deze boom niet steeds op te hoeven bouwen, maar opslaan in een bestand
Nog liever zou ik het direct op slaaan in de executable, zodat geen tijd hoeft verloren te gaan met inlezen tree.

Ik weet alleen niet hoe ik dat moet doen. Wie helpt me?

[ Voor 3% gewijzigd door hemaworst op 15-02-2005 20:52 ]

[djluc]

Ik begrijp dit er uit:
Je hebt een textfile en wilt die omzetten naar dezelfde tekst maar dan in de van de bijbehorende nummers?

[Genoil]

als je de tree nou opslaat in een database hoef je niet telkens die textfile te parsen.
http://www.vieka.com/esql.htm

[Verwijderd]

Per woord kijk ik wat de T9 code is

Volgens mij doe je 't verkeerd om: als je per T9 code kijkt welke woorden binnen dat filter passen, moet 't een stuk sneller gaan. Zeker wanneer je dynamisch het filter bijstelt wanneer een nieuw cijfer wordt ingevoerd.

Waarom iemand overigens T9 op een PDA zou willen ontgaat me, maar het zal wel z'n nut hebben of zo...

[MrBucket]

Verwijderd schreef op dinsdag 15 februari 2005 @ 21:18:
[...]

Volgens mij doe je 't verkeerd om: als je per T9 code kijkt welke woorden binnen dat filter passen, moet 't een stuk sneller gaan. Zeker wanneer je dynamisch het filter bijstelt wanneer een nieuw cijfer wordt ingevoerd.

Volgens mij doet TS dat al. Tenminste, ik neem aan dat m_woorden van de TreeNode alleen die woorden bevat die aan het afgelegde pad binnen de boom voldoen? (dwz, voor het voorbeeld "42556", als je bij de node "6" bent aangekomen bevat m_woorden alleen de woorden die gespeld kunnen worden met de cijfercombinatie "42556"?)

Zo ja, dan is dit iig de snelste manier om, als de file eenmaal ingelezen is, cijfercombinaties om te zetten in mogelijke woorden.

Qua inlezen zie ik ook niet zo snel mogelijkheden tot performance-verbetering, behalve idd de opgebouwde boom te serializen.

Mag ik vragen in welke programmeertaal je dit doet?

[.oisyn]

Afterlife: je leest verkeerd, hij heeft het over het inlezen van de boomstructuur. Hij leest nu gewoon een woordenlijst in, en dus moet ie bij elk woord de t9 code vinden om de boomstructuur te creëren.

hemaworst: Je kunt de boomstructuur toch gewoon opslaan? Implementeer in je treenode een serializeerfunctie die al z'n kinderen (via hun serializeerfunctie) en z'n woordenlijst opslaat. Natuurlijk wel even rekening houden met null nodes, het is wellicht handig om voor het serializeren van de kinderen eerst aan te geven welke kinderen geldig zijn en welke null, bijv. met een bitpatroon van 8 bits voor de 8 kinderen. Tijdens het inlezen kun je dan zien welke hoeveel kinderen er komen gaan en onder welke toets die kinderen zitten.

[Soultaker]

Je hebt de boom in een trie-formaat in het geheugen; als je 'm ook op zo'n manier opslaat kun je in principe de hele look-up vanaf de schijf doen (niet superefficient, maar wel acceptabel).

Verder hoop ik dat je zelf ook bedacht had dat als je de woorden sorteert op hun (uniek bepaalde) T9 code, dat met woorden die in aanmerking komen steeds een aansluitende deelverzameling zijn van de lijst die je ervoor had en dat in die lijst de woorden die een directe match opleveren (omdat ze dezelfde lengte hebben als de ingevoerde T9-code) bovendien bovenaan staan.

Je kunt dus een aparte op T9-code gesorteerde woordenlijst maken waar elk woord één keer in voorkomt. Per node hoef je dan alleen maar het nummer van het eerste en laatste woord op te slaan dat ervoor in aanmerking komt.

edit:
Ik bedenk me net dat voor T9 alleen de 'directe' matches van belang zijn, dus dan maakt het niet echt uit hoe je die opslaat (die kun je gewoon per node opslaan).

[ Voor 11% gewijzigd door Soultaker op 15-02-2005 22:06 ]

[Verwijderd]

.oisyn schreef op dinsdag 15 februari 2005 @ 21:42:
Afterlife: je leest verkeerd, hij heeft het over het inlezen van de boomstructuur. Hij leest nu gewoon een woordenlijst in, en dus moet ie bij elk woord de t9 code vinden om de boomstructuur te creëren.

Ehmm... uit het bericht van TS:

Per woord kijk ik wat de T9 code is

Da's volgens mij doodgewoon verkeerd om. Je moet per T9-reeks kijken welke woorden daaraan voldoen, en daarop filteren.
En een boomstructuur lijkt me hier ook niet handig: gewoon zo plat mogelijk houden:
een lijst van T9-codes plus bijbehorende woorden, gesorteerd op T9-code.

Tik in '2', en je hebt direct een filter op zeg 5000 woorden.
Tik in '26', en het worden er opeens maar 500. En die hoef je niet eens uit de hele woordenlijst te halen, maar uit die 5000 die je al gefilterd had.

edit: Nog 's nagelezen, en ik las 't inderdaad verkeerd.
Neemt niet weg dat m'n idee om het zo plat mogelijk te houden blijft staan.

[ Voor 9% gewijzigd door Verwijderd op 15-02-2005 22:59 ]

[.oisyn]

Verwijderd schreef op dinsdag 15 februari 2005 @ 22:33:
En een boomstructuur lijkt me hier ook niet handig: gewoon zo plat mogelijk houden:
een lijst van T9-codes plus bijbehorende woorden, gesorteerd op T9-code.

Tik in '2', en je hebt direct een filter op zeg 5000 woorden.
Tik in '26', en het worden er opeens maar 500. En die hoef je niet eens uit de hele woordenlijst te halen, maar uit die 5000 die je al gefilterd had.

Hoe 'direct'? Hoe krijg je direct die 5000 woorden bij een input van '2'? Daar ben ik eigenlijk wel benieuwd naar. De boomstructuur heeft een opzoektijd die lineair is aan het aantal tekens van de invoer. Aangezien er al een reactie is gewenst na elke toets die wordt ingedrukt kun je per toets dus je woordenlijst in constante tijd opzoeken.

Daarnaast zul jij de woorden, of iig de referenties ernaar, dubbel opgeslagen moeten worden. Bij de boomstructuur kun je mbv een iterator gewoon alle woorden binnen een bepaald bereik afgaan.

[Verwijderd]

.oisyn schreef op Wednesday 16 February 2005 @ 00:15:
Hoe 'direct'? Hoe krijg je direct die 5000 woorden bij een input van '2'? Daar ben ik eigenlijk wel benieuwd naar.

Je hebt in feite alleen pointers naar het eerste en laatste record nodig die voldoen aan het filter "T9-code begint met '2'". Da's aardig direct, lijkt me.
En als je vervolgens '26' hebt ingetikt, weet je dat je niet buiten die al gevonden pointers hoeft te zoeken, dat scheelt ook in zoekacties.

Daarnaast zul jij de woorden, of iig de referenties ernaar, dubbel opgeslagen moeten worden. Bij de boomstructuur kun je mbv een iterator gewoon alle woorden binnen een bepaald bereik afgaan.

Dubbel opslaan is niet nodig, alleen die 2 pointers hoef je te bewaren. En dan kun je ook prima itereren van eerste naar laatste record om de woorden te vinden.
Boomstructuren zijn vaak ontzettend handig, maar in dit geval gewoon overdone: leaf '26' hoeft niet te weten dat 'ie onder leaf '2' hangt, de lijst weet nl. al dat '26' ergens tussen '2' en '3' zit. En dat is in dit geval (met een steeds fijnmaziger filter naarmate je meer cijfers intikt) meer dan voldoende, omdat het filter toch lineair blijft t.o.v. de lijst. Pointers naar eerste en laatste record binnen het filter is te allen tijde voldoende.

[Kuhlie]

DeMijn oplossing is al bijna gezegd. Hoe ik het gedaan heb is als volgt: ik heb een bestand gegenereerd met als inhoud:

2a
7as
28au
33de
343die

etcetera. Wat je doet: je opent het bestand en gaat 'halveren', je begint halverwege het bestand en zoekt dan naar de eerste newline. Vanaf daar lees je tot aan de eerste letter, je hebt dan een cijferreeks, bijv. 39858. Is die reeks 'meer' dan de invoer dan halveer je de positie, is het 'minder' dan doe je positie keer 1,5. Op die manier kom je in logaritmische tijd uit op de plek waar je wil zijn. Bovendien kost het nauwelijk geheugen omdat je de informatie gewoon direct uit het bestand haalt.

[ Voor 9% gewijzigd door Kuhlie op 16-02-2005 09:14 . Reden: voorbeeld gefixt, en iets minder lompe eerste zin gemaakt :P ]

[MrBucket]

Verwijderd schreef op Wednesday 16 February 2005 @ 08:28:
[...]

Je hebt in feite alleen pointers naar het eerste en laatste record nodig die voldoen aan het filter "T9-code begint met '2'". Da's aardig direct, lijkt me.
En als je vervolgens '26' hebt ingetikt, weet je dat je niet buiten die al gevonden pointers hoeft te zoeken, dat scheelt ook in zoekacties.

En hoe kom je aan de start- en eind-pointers voor "T9-code begint met 2"? Een binary search door de gehele woordenlijst? Dat is logaritmisch in het aantal woorden (ter vergelijking: 2log(130.000) is nog steeds 17 stappen, dus 34 stappen om de begin- en eindpointers te vinden).

Deze pointers vanaf het begin opslaan helpt je niet veel, want dan zit je bij het 2e cijfer met hetzelfde probleem, dan moet je daarna alsnog een binary search doen binnen de begin- en eind-pointers. Zou je die ook opslaan, dan moet je bij het 3e cijfer alsnog een binary search doen (etc.). Als je alle begin- en eind-pointers van tevoren opslaat, heb je eigenlijk weer de T9-boom te pakken.

Bij de T9-boom is het opzoeken van de mogelijke woorden lineair in het aantal karakters. Daar kan geen binary search tegenop.

[MrBucket]

Ok, nu dan even voor TS: hoe sla je zo'n boom op.

Het principe is hetzelfde als hoe de boom is opgeslagen in het geheugen, nl. met pointers. Punt is alleen dat het geen zin heeft om geheugenadressen weg te schrijven in een file (want je weet niet op welke plek in het geheugen je het bestand straks weer inleest). Dus: als pointers moet je de positie van een node / woordenlijst binnen de file gebruiken (bijv.: node "34" staat op 36754 bytes vanaf het begin van de file).

Een mogelijke aanpak is, zoals .oisyn al aangaf, elke node zichzelf te laten serializen. Dit is het makkelijkst om recursief te implementeren, zoals:

code:

typedef unsigned int FileOffset;
struct SerializedT9Node{
  FileOffset m_keys[8];
  FileOffset m_words;
};

FileOffset T9Node::Serialize(ByteStream &bs){
  FileOffset foThisNode, foChildNode, foWords;

  //Allocate space for the current node in the bytestream
  bs << SerializedT9Node();
  foThisNode = bs.size() - sizeof(SerializedT9Node);

  //Serialize first child, and update FileOffset in foThisNode
  if(m_key2 != NULL)
    foChildNode = m_key2->Serialize(bs);
  else
    foChildNode = NULL;
  ((SerializedT9Node *)&bs[foThisNode])->m_keys[0] = foChildNode;

  //Serialize second child, and update FileOffset in foThisNode
  if(m_key3 != NULL)
    foChildNode = m_key3->Serialize(bs);
  else
    foChildNode = NULL;
  ((SerializedT9Node *)&bs[foThisNode])->m_keys[1] = foChildNode;

  //Etc.

  //Serialize words (requires that m_woorden also has a Serialize() member)
  if(m_woorden != NULL)
    foWords = m_woorden->Serialize(bs);
  else
    foWords = NULL;
  ((SerializedT9Node *)&bs[foThisNode])->m_words = foWords;

  //Return start of current node within ByteStream
  return foThisNode;
}

Ik ben ervan uitgegaan dat ByteStream een std::vector<unsigned char> is, die met de '<<'-operator je eigen datatypes (zoals SerializedT9Node) kan toevoegen (aan het eind van de stream).
Let erop dat ik eerst een lege SerializedT9Node toevoeg aan de stream en vervolgens, bij het serializen van elke child-node de juiste FileOffset van deze lege SerializedT9Node bijwerk.

[ Voor 3% gewijzigd door MrBucket op 16-02-2005 11:35 . Reden: Code-tag doet raar? ]

[.oisyn]

Verwijderd schreef op Wednesday 16 February 2005 @ 08:28:
[...]

Je hebt in feite alleen pointers naar het eerste en laatste record nodig die voldoen aan het filter "T9-code begint met '2'". Da's aardig direct, lijkt me.
En als je vervolgens '26' hebt ingetikt, weet je dat je niet buiten die al gevonden pointers hoeft te zoeken, dat scheelt ook in zoekacties.

Maar je hebt nog steeds zoekacties, ergo, het performt langzamer dan een zoekboom.

Boomstructuren zijn vaak ontzettend handig, maar in dit geval gewoon overdone: leaf '26' hoeft niet te weten dat 'ie onder leaf '2' hangt, de lijst weet nl. al dat '26' ergens tussen '2' en '3' zit.

En hoe weet ie waar 3 begint? En hoe weet ie waar 365 begint en eindigt? Met een boom kost je dat welgeteld 3 node fetches, jij moet een binaire search gaan doen naar die 365.
En waarom is een boom overdone? Hij is sneller en kost net zoveel geheugen als jouw oplossing, ik zou niet weten waardoor dat overdone is, zeker op een device waar je wat minder processorkracht tot je beschikking hebt.

[Soultaker]

Je hoeft helemaal niet te weten waar 3 begint of waar 365 begint of eindigt. In de telefoons die ik ken krijg je voor een T9 code alleen de woorden die exact die T9-code hebben te zien en verder niets. Elke datastructuur waarmee je een T9 code naar een lijst woorden kunt mappen volstaat dus in principe.

[MrBucket]

Soultaker schreef op woensdag 16 februari 2005 @ 14:12:
Je hoeft helemaal niet te weten waar 3 begint of waar 365 begint of eindigt. In de telefoons die ik ken krijg je voor een T9 code alleen de woorden die exact die T9-code hebben te zien en verder niets. Elke datastructuur waarmee je een T9 code naar een lijst woorden kunt mappen volstaat dus in principe.

Het kan ook wel, maar zo'n mapping is gewoon minder efficient.
Voor jouw oplossing kost elk cijfer wat je intoetst O(log n) zoektijd (met n het aantal woorden in je woordenlijst). Voor een woord uit k karakters is dit dus O(k log n) tijd, misschien iets minder als je handig met pointers omgaat, maar nog altijd logaritmisch.

Vergelijk dit met de T9-boom. Daar is voor elk cijfer dat je intoetst 1 pointer volgen voldoende. Ergo, je zoektijd voor een woord van k karakters is O(k), m.a.w. linear in het aantal letters in je woord, en dus onafhankelijk van het totaal aantal woorden in je woordenlijst. Veel sneller dus.

[Soultaker]

Als je in de thread kijkt, zie je dat mijn eerste voorstel ook was om gewoon de trie op te slaan, en dan krijg je inderdaad de performance die jij bespreekt.

Verder ga jij er vanuit dat de dictionary in een binaire boom opgeslagen staat. Dat is natuurlijk niet handig; voor een on-disk boomstructuur wil je waarschijnlijk een B-tree formaat gebruiken. Als je uitgaat van blokken van 512 bytes (wat vrij gangbaar is) dan is een branching factor van 16 ofzoiets best realistisch (dan heb je 32 bytes per entry, ruim voldoende voor een 4 byte pointer en een woord van maximaal 28 karakters) en dan hoef je dus maar log₁₆(N) accessess te doen. Dat is met de gegeven woordenlijst van 130.000 woorden slechts 4 a 5 operaties; gemiddeld maar iets meer dan de trie dus.

Maar het echte punt was dat je een (niet noodzakelijkerwijs minimale) perfecte hash functie voor je woordenlijst kunt kiezen, de parameters daarvan makkelijk in je geheugen houden, en dan in één keer de positie van de lijst met woorden voor een gegeven T9-code hebt! Dat is dus gewoon een enkele operatie.

edit:
Even voor de duidelijkheid: de trie-gebaseerde methode is nog steeds iets beter als je niet voor elke code opnieuw begint te zoeken, maar zoals MrBucket voorstelde een pointer bijhoudt die je steeds update. Maar het verschil is klein en zit 'm niet in een verschil in complexiteit.

[ Voor 17% gewijzigd door Soultaker op 16-02-2005 17:39 ]

[Verwijderd]

.oisyn schreef op woensdag 16 februari 2005 @ 11:51:
En hoe weet ie waar 3 begint? En hoe weet ie waar 365 begint en eindigt? Met een boom kost je dat welgeteld 3 node fetches, jij moet een binaire search gaan doen naar die 365.
En waarom is een boom overdone? Hij is sneller en kost net zoveel geheugen als jouw oplossing, ik zou niet weten waardoor dat overdone is, zeker op een device waar je wat minder processorkracht tot je beschikking hebt.

Laten we het er maar op houden dat de waarheid ergens in het midden ligt...
Een boom neemt altijd meer ruimte in dan een platte lijst (je moet nl. ook ergens de links bijhouden), en in een platte lijst moet je meer zoeken dan in een boom (al is dat in dit geval goed te optimaliseren door gebruik te maken van het filter van de vorige selectie).

Geheugengebruik is belangrijk bij een PDA, en dan "wint" de platte lijst. Een typische PocketPC met 64MB geheugen heeft bv. standaard maar 20MB werkgeheugen ter beschikking, en dat is voor programma's en data samen.

Zoeken in een boom gaat sneller dan een binary search in een platte lijst, en da's wel prettig wanneer de processor niet zo snel is. Al zijn de moderne PDA's niet meer zo langzaam als de oude Palmpjes.

Ik heb die zoeksnelheid op een platte lijst overigens even getest op m'n PDA'tje:
ASCII versie van een postcode tabel uit '99 (112MB groot, 617.000 records), en gemiddeld duurde 't minder dan 0.2 seconden om het juiste record bij een postcode te vinden. Lijkt me zeer acceptabel, en het voelt gewoon 'direct' aan.

Eerlijk gezegd was die test wel op een 'boven gemiddelde' PDA (Asus A730W, 520MHz XScale processor, 128MB geheugen, en de tabel stond op een snelle APacer Steno CF-kaart). Ik zal 't morgen 's testen op m'n andere PDA (HP 5450, 64MB en een langzaam SD-kaartje)...

O ja, nog een voordeel van een platte lijst: de lijst zelf kan dan gewoon het data-bestand zijn, en je hoeft niets naar een boomstructuur om te zetten. Scheelt een enorme hoop geheugen.

[.oisyn]

Verwijderd schreef op woensdag 16 februari 2005 @ 23:39:
Een boom neemt altijd meer ruimte in dan een platte lijst (je moet nl. ook ergens de links bijhouden), en in een platte lijst moet je meer zoeken dan in een boom (al is dat in dit geval goed te optimaliseren door gebruik te maken van het filter van de vorige selectie).

En daarom laadt je de boom niet in z'n geheel in het geheugen, wat ook meteen een ander voordeel is van een boom tov een platte lijst (makkelijk te doorzoeken, zelfs in een bestand) . Zie Soultaker in "[ALG] T9 Boom structuur opslaan in besta..." voor meer info

[ Voor 9% gewijzigd door .oisyn op 17-02-2005 11:04 ]

[Polderdijk]

Ga je het gebruiken op een pocketPC met WindowsCE erop?

Zo ja dan kan je veel beter de woorden database inlezen in de inwendige database (soort MSDE/MSSQL). Hiermee kan je gewoon in je code de database oproepen met een SQL statement en krijg je véél sneller je woorden terug.

Je kan op deze manier gewoon simpel filtertjes leggen en heb je geen problemen!

[hemaworst]

He wat een hoop replies! Thanks!

Mijn gedacht tot nu toe:

1) Geheugen
Wanneer ik mijn boom serialize door nodes zichzelf te laten serializen dan kan de boom op schijf blijven, dus hoeft niet in geheugen.
Een lijst hoeft ook niet in geheugen te worden geladen dus conclusie op dit punt:
Geen voorkeur

2) ik heb even een delphi prototype gemaakt met het "halveer" principe om een woord te zoeken. Dat werkt erg goed. Geen zichtbare vertragingen .(zijn ook steeds slecht 20 zoek acties). Ik neem aan dat de pocketpc dit ook razend snel kan.

3) Bomen serializen vind ik een mooi idee. Vergt alleen meer opslag ruimte. Ook is het bestand met woorden dan slecht voor de gebruiker aan te passen.

4) database indexen gebruiken. Idee klinkt het makkelijkst, db's hebben ingebouwde index(btree's?) dus lekker snel. maar vind ik ook de minst mooie oplossing, geen uitdaging.

Conclusie tot nu toe:
Een lijst is onefficienter dan een boom, maar resulteerd niet in een merkbare vertraging tov een boom.
Een lijst is veel makkelijker aan te passen door een computer leek
Ik denk dat ik nu voor de lijst ga, alhoewel ik een boom stoerder vind

bedankt tot zo ver! Ik post het resultaat wel hier

[ Voor 4% gewijzigd door hemaworst op 17-02-2005 19:34 ]