Om nieuwe domeinnaamideeën voor te stellen en te genereren, moeten we kunnen herkennen uit welke woorden een domeinnaam bestaat. Woordsegmentatie is een techniek uit natuurlijke taalverwerking die meestal wordt gebruikt om woorden te vinden in tekenreeksen uit talen zonder natuurlijke woordgrenzen, zoals Chinees of Japans. Wij gebruiken deze techniek om de woorden ‘Instant Domain Search’ te vinden in domeinen zoals instantdomainsearch.com. De Python-bibliotheek wordsegment lost dit probleem op, maar we moesten die naar Rust overzetten om haar snel genoeg te maken voor Instant Domain Search.
Wordsegment is gebaseerd op het woordsegmentatievoorbeeld van Peter Norvig in Beautiful Data. Het basisidee is dat je alle mogelijke segmentaties van een tekenreeks doorloopt en beoordeelt op de kans dat ze in echte teksten voorkomen. Daarvoor hebben we twee onderdelen nodig:
- Een manier om de kans te schatten dat een zin in de echte wereld voorkomt.
- Een efficiënte manier om alle mogelijke segmentaties van de invoertekenreeks te beoordelen.
Laten we bekijken hoe beide werken.
Een zin scoren
De eenvoudigste manier om segmentaties te beoordelen, is afzonderlijke woorden scoren op hun kans om in echte Engelstalige gegevens voor te komen. Norvig gebruikte een Google-dataset genaamd Google Trillion Web Corpus (2006). De Web 1T-collectie is openbaar beschikbaar, uitsluitend voor onderzoek en onderwijs. Die gebruikte ik aanvankelijk voor onze port.
Om de score voor één woord te krijgen, deel je het aantal voorkomens van dat woord in het corpus door het totale aantal woordvoorkomens. Het woord ‘instant’ kwam bijvoorbeeld ongeveer 28 miljoen keer voor in Web 1T. Het corpus dat we gebruiken bevat in totaal ongeveer 588 miljard woorden, omdat zelden voorkomende woorden uit de lange staart ontbreken. We schatten de kans op ‘instant’ daarom op 0.000049. Ook woorden die niet in het corpus voorkomen moeten een score krijgen. Lees voor details het hoofdstuk van Norvig.
De volgende stap is een reeks woorden scoren. Daarvoor zouden we de kansen van alle woorden in de invoerzin kunnen vermenigvuldigen. Om rekenfouten door vermenigvuldiging van veel kleine getallen te voorkomen, nemen we in plaats daarvan de logaritme met grondtal 10 van elke waarde en tellen die op. Voor ‘this is a test’ geeft dat -2.3 + -2.1 + -1.8 + -3.6 = -9.7. De formule voor woorden die niet in het corpus staan geeft daarentegen -22 voor ‘thisisatest’.
Om resultaten verder te verfijnen, nemen we net als Norvig ook bigrammen mee: de voorwaardelijke kans dat twee woorden naast elkaar voorkomen. Voor elk woord behalve het eerste bekijken we niet de eenvoudige kans dat het woord voorkomt, maar de kans dat het na het vorige woord verschijnt. Met het oorspronkelijke corpus krijgt ‘is’ na ‘this’ een score van -3.2 in plaats van -2.1. Zo verfijnt context onze scores.
Segmentaties opsommen
Voor korte tekenreeksen willen we alle mogelijke segmentaties opsommen om de best scorende splitsing te vinden. Maar het aantal segmentaties groeit exponentieel met de lengte van de invoer, waardoor dit voor langere reeksen onhaalbaar wordt. Tegelijk zijn heel lange woorden steeds onwaarschijnlijker. Daarom stellen we eerst een maximale woordlengte van 24 tekens vast. Vervolgens splitsen we de invoer op elk van de eerste 24 tekengrenzen en tellen we de score voor het eerste woord op bij de score voor de resterende woorden.
Norvig gebruikte recursie, net als onze eerste Rust-versies. Onlangs hebben we onze implementatie aangepast op basis van Wolf Garbes artikel Fast Word Segmentation of Noisy Text. We gebruiken nu een variant van het daarin besproken algoritme met een driehoeksmatrix. In onze implementatie houdt een array met dynamische grootte, Rusts Vec, de beste score op elke segmentatiepositie bij. Voor ‘thisisatest’ heeft de kandidaat voor positie 6, na ‘is’, bijvoorbeeld een lengte van 2 en de score voor ‘this is’. Deze aanpak begrenst de stackgrootte. Ik vind de geneste lussen bovendien gemakkelijker te begrijpen dan begrensde recursie. We pasten de driehoeksmatrixaanpak aan om bigramscores mogelijk te maken.
Prestatie-optimalisaties
Op mijn computer kan de Python-bibliotheek wordsegment ‘thisisatest’ eens per 500 µs segmenteren. De nieuwste versie van instant-segment doet hetzelfde in 4 µs: 95 keer sneller met hetzelfde werk. Hieronder een aantal technieken die we gebruikten.
- De eerste port was maar 1,7 keer sneller dan de Python-code. Die gebruikte dezelfde recursieve aanpak voor segmentaties als wordsegment en Norvigs code, met een hashmap om deelscores te cachen. Zo bereken je de scores voor ‘thisis a test’ en ‘this is a test’ sneller als je de score voor ‘a test’ hergebruikt.
- Door onnodige allocaties in de hoofdlus te vermijden en voor de cache over te stappen op ahash, kwamen we op 4,9 keer de Python-snelheid.
- De crate smartstring voorkomt heapallocaties voor korte tekenreeksen en past goed bij dit probleem, omdat woorden doorgaans kort zijn. Daarmee haalden we 9,0 keer de Python-snelheid.
- Het inline plaatsen van de hoofdlus die segmentatieposities oplevert bracht ons op 11 keer de Python-snelheid.
- Herhaalde allocaties voor tussenresultaten vermijden hielp ons naar 12 keer.
- Rust-tekenreeksen zijn UTF-8-gecodeerd, dus het uitsnijden van delen vereist validatie van tekenposities. Maar instant-segment weigert invoer met niet-ASCII-tekens. Met een beetje unsafe-code om Unicode-validatie over te slaan, kwamen we op 15 keer.
- Een update naar een nieuwere versie van ahash bracht ons op 18 keer.
- Overstappen van f64::powf() naar f64::powi() hielp ons naar 19 keer.
- Tussenallocaties hergebruiken bij meerdere opeenvolgende segmentaties bracht de prestaties op 25 keer sneller dan Python.
- Tot slot bracht de driehoeksmatrixaanpak ons op 95 keer.
instant-segment
We hebben dit werk als opensource beschikbaar gemaakt. De nieuwste versie van instant-segment is beschikbaar op crates.io. Dit jaar voegden we Python-bindings toe met het uitstekende PyO3. Ook pasten we de testdataset in onze repository aan, zodat die is gebaseerd op recentere datasets met vrijere licenties van Google en het SCOWL-project. Daardoor is beginnen met instant-segment gemakkelijker dan ooit. We horen graag je feedback en hoe je het project gebruikt!