Autokomplet søgning i høj kvalitet, del 1.

Leverer relevante resultater til millioner af kunder

Traveloka hotel autofuldførelse.

Har du søgt efter hoteller i Traveloka?

Jeg ved, at du har prøvet den autofuldførte søgning. Faktisk er Autocomplete-søgning den vigtigste gateway til at udforske myriader af Traveloka-hoteller. Ved at bruge hotel autokomplet søgning får brugerne det mest relevante hotel, region og vartegn som-du-type. Autofuldførelse hjælper brugere med at spare tid, mens du skriver og minimerer chancerne for stavefejl, hvilket resulterer i en bedre kundeoplevelse generelt, derfor er det vigtigt for Traveloka at have en autokomplet søgning i høj kvalitet.

Der er dog flere udfordringer, der skal håndteres af hotellets autofuldførelse.

For det første forventes automatisk autofuldførelse at give de mest relevante resultater ved hjælp af mindst mulig tastetryk.

For det andet, da Traveloka har at gøre med internationale brugere, skal autofuldfør søgning være i stand til at håndtere forskellige sprogspecifikke forældre, såsom i thailandske sprog, ord skrives uden mellemrumsskiller f.eks. Ko ko (ko samui).

For det tredje skal autofuldførelse også være hurtig. Ligegyldigt hvor god autofuldførelse er, vil brugeroplevelsen ikke være sjov, hvis det tager for lang tid at give resultater.

At tackle udfordringerne

1. Formulering af relevans score

Brugere vil kun se de mest relevante resultater. Derfor er den måde, relevansscorealgoritmen fungerer på, en af ​​nøglerne til automatisk udfyldt søgning.

1.1 Klassisk måde at score tekst relevans score

Den klassiske måde at beregne relevansscore er baseret på termfrekvens (tf), invers dokumentfrekvens (idf) og feltlængde-norm.

Termfrekvens betyder, at jo hyppigere et udtryk vises, jo mere betydning er det, f.eks. Tekst "Bora bora ø" er mere relevant end "boracay ø" for forespørgsel "bora".

Kamp om termfrekvens, Bora-Bora vs Boracay. [kilde]

Omvendt dokumentfrekvens indebærer, at et ords relative vægt er relateret til det inverse af dets forekomster i alle dokumenter, hvilket gør mere almindelige ord mindre betydningsfulde end det usædvanlige. For eksempel i teksten "Eiffeltårn" bærer ordet "Eiffel" mere vægt end "tårn", fordi "tårn" er meget mere almindeligt og generelt end "Eiffel".

Feltlængde-norm beskriver, at jo længere teksten er, desto mindre signifikant sammenlignes den med de kortere. fx tekst kaldet “Jakarta” er mere markant end “West Jakarta”, fordi “Jakarta” er kortere end “West Jakarta” for forespørgsel “Jakarta”.

Derfor kan den klassiske måde til relevans score formel sammenfattes med

Relevansscore = Tf * Idf * -norm

1.2 Forbedring med BM25

Den klassiske måde at beregne relevans er et stort skridt fremad. For et kort felt - typisk for traveloka-enheder - bør den relative betydning af hver faktor (tf, idf og norm) imidlertid ikke behandles ens, ellers fører det til forkerte resultater. I korte tekster er det meget bedre at dæmpe effekten af ​​Tf og feltnorm sammenlignet med Idf.

For at tackle dette problem bruger vi BM25 som en grundlæggende måde at beregne relevans score på. BM25 er i sig selv en ganske omfattende metode (wikipedia), men ved at bruge BM25 kan den relative betydning af hver faktor (Tf, Idf og feltlængde-norm) justeres.

1.3 Varierende boost for alle felter.

Eksempel på et vartegn. Kan du gætte, hvilken der hedder navn, alias og yderligere oplysninger?

En dokumentenhed består af flere felter som navn, alias, yderligere oplysninger. Hvert felt skal have forskellige vægte, f.eks. Navnefelt skal være vigtigere end alias og yderligere info. Derfor giver matching med navnefelter bedre score end at matche med yderligere infos eller aliasfelt.

1.4 Tilføjelse af popularitet og geoLocation baseret boosting

For yderligere at forbedre søgeresultatet, indstiller vi den beregnede score med popularitetsdata og geolocation.

At øge efter popularitet betyder, at de mere populære dokumenter får scoringer med større relevans sammenlignet med de mindre populære dokumenter, ellers er andre ting ens. Dataene kan udledes af forskellige aspekter, især mængden af ​​brugersøgning. Yderligere skal popularitetsdata også oprettes pr. Landestand, da popularitet er lokaliseringsspecifik.

Popularitet tages også i betragtning. Det er også landespecifikt.

Vi øger også relevansresultatet efter brugers placering. Resultater, der er placeret i den samme region som brugerens, får et yderligere løft.

Brugere har en tendens til at være interesseret i resultater i nærheden.

1.5 Tilføjelse af eksakt boost.

Selvom ovenstående faktorer synes tilstrækkelige, kunne vi øjeblikkeligt finde en alvorlig mangel i algoritmen. Da det understreger popularitetsdata, ender mange upopulære enheder altid i bunden af ​​søgeresultatet, uanset hvor nøjagtige forespørgslen er, hvilket gør upopulær enhed næppe søgbar.

Dette problem forværres på hoteller, da de normalt har excentriske navne. De har måske navne som "hotel j", "hotel i", "hotel m" osv. Baseret på popularitet alene giver forespørgsel "hotel j" normalt "hotel jxxx" (den mest populære) øverst på listerne , hvilket efterlader “hotel j” tæt på bunden på grund af dets lave popularitet.

Hotel J eller Hotel Jxxx?

For at afhjælpe dette problem tilføjer vi boost til de enheder, der nøjagtigt matcher selve forespørgslen. For eksempel når brugeren spørger om "hotel j", får hotel med nøjagtige udtryk "hotel j" yderligere løft.

2. Håndtering af menneskelige sprog

Autofuldfør søgning er relateret til den måde, mennesket interagerer med sprog på. Derfor skal en masse ting implementeres og passe på sammenlignet med en ikke-tekstsøgning.

2.1 Analyseproces

Det første trin i en tekstsøgning er at analysere teksten. I denne proces omdannes teksten til enkle søgbare tokens. Analysering består af flere trin, såsom tokenisering, stemming, synonym og helvedesildbehandling.

en. Tokenizing

Tokenisering betyder at opdele teksterne i mindre søgbare tokens. Tekstseparatoren skal ikke kun være whitespaces, men også tal, symboler og andre ikke-numeriske tegn, da brugere normalt behandler dem som en separator.

Følgende eksempel er ret almindeligt i brugersøgning:

Eksempel på tekster og deres symboler.

b. Tilsyn

I stemming process reduceres ord til dets grundlæggende form, f.eks. "Spise" til "spise", "købe" til "købe".

c. Synonym

I synonymprocessen udvides ordene til dets synonym, hvilket gør tokens også søgbare med deres synonymer.

d. Shingle

Med eller uden plads?

Undertiden søger bruger også ordene uden mellemrum. F.eks. Skal "Hong Kong" -dokument også kunne søges med nøgleordet "Hongkong" (uden plads). Derfor løses problemet ved en helvedesildsproces, der kombinerer tilstødende symboler.

2.2 Specifikke sprogfunktioner

Som forklaret tidligere har flere sprog deres egne særegne egenskaber. På thailandske sprog skrives ord uden mellemrumsskiller som เกาะสมุย (ko samui). Denne opførsel vil mislykkes med det mellemrum baserede analysator på grund af manglen på tilsyneladende token separator. Løsningen? Brug specifik sproganalysator til at analysere tekst fra forskellige sprog. Ved at bruge thailandske analysator bliver teksten เกาะสมุย tokeniseret til เกาะ (koh) og ส มุ ย (samui).

2.3 Typohåndtering

Det er ganske almindeligt, at brugere ikke kender den nøjagtige tekst, de leder efter, hvilket gør dem tilbøjelige til skrivefejl. Derfor skal autofuldførende system også være i stand til at foreslå dem ikke kun de dokumenter, der indeholder de nøjagtige symboler, men også dem, der ligger ganske tæt på forespørgslen.

For at tackle dette problem bruger vi fuzzy forespørgsel, der tillader, at tekst, der er inden for en bestemt Levenshtein-redigeringsafstand (slet, indsæt og swap), kan betragtes som match.

ElasticSearch fuzzy forespørgsel

For det sidste tryk, ønsker vi ikke at give dokumenter, der blev matchet via skrivefejl for at have en høj relevansscore, hvorfor dokumenter, der matches med uklar forespørgsel, fik lavere boost.

3. Oprettelse af et autocomplete-system med høj ydeevne

Et sofistikeret autokomplet system ville være meningsløst, hvis det tager for meget tid at producere resultater. Desuden vil et langsomt autofuldførende system også skabe en ubehagelig brugeroplevelse - noget at undgå for enhver pris.

Der er mange måder at forbedre latensydelsen af ​​autofuldførelse, som i sig selv er et interessant emne at dække i en separat blog. En af dem er blot at flytte den beregningsintensive del fra forespørgselstid til indekseringstid. Det er vigtigt, at forespørgselstiden er hurtig og hurtig, mens indekseringstiden ikke har nogen indflydelse på brugeren.

For resten kan du holde øje med den anden del af denne blog, hvor jeg vil diskutere om systemarkitektur og løsning til højtydende autofuldførende tjenester.

Jeg er heldig som står over for denne fascinerende, åbne søgealgoritmeudfordring med mit team hos Traveloka, et af de største online rejsefirmaer i Sydøstasien. Hvis du er en softwareingeniør, der er interesseret i at udvikle det nyeste søgesystem, som hjælper millioner brugere med at finde deres næste eventyr, kan du se på mulighederne på Travelokas karriere-side!

Særlig tak til Jogie for diskussionen om den forrige autokomplette implementering, Yosef Sidharta, for at udfordre algoritmen med mange brugersager og Evan Yonathan for den uvurderlige vejledning.