bild
Skolan för
elektroteknik
och datavetenskap

Språkteknologi

Stavningskontroll

Viggo Kann

Kortfattat innehåll

Beskrivning av programmet Stava. Algoritmer och datastrukturer för snabb sökning i och kompakt lagring av ordlistor.

Litteratur

Bredvidläsningslitteratur
  • Techniques for automatically correcting words in text av Karen Kukich, ACM Computing Surveys 24, sida 377-439, 1992.
  • Detection of spelling errors in Swedish not using a word list en clair av Domeij, Hollman, Kann, 1994.

Föreläsningsanteckningar

Föreläsningsanteckningarna finns här.

Innehåll

  • Definition av rättstavningsproblemet.
  • Skillnad mellan lingvistiska och statistiska angreppssätt på rättstavningsproblemet.
  • Effektiv lagring av ordlistan med Bloomfilter.
  • Hantering av sammansättningar med hjälp av tre ordlistor
    • isolerade ord
    • förled
    • efterled
  • Hantering av böjningsformer och avledningar med suffixregler.
  • Generering av rättelseförslag.
    • Olika metrik (avståndsmått mellan ord) för olika typer av text.
    • Grafotaktisk tabell med bokstavsfyrgram förhindrar övergenerering av förslag.
    • Metoder för rangordning av rättelseförslag.
  • Optimering.
    • Optimering av hashfunktionen.
    • Effektiv lagring av frekvensinformation.
    • Effektiv sökning bland suffixreglerna.
  • Konstruktion av suffixregler.
  • Säkerhetsaspekter på lagringen av ordlistor.

Exempel på tentafråga

Fråga

Ge exempel på två metoder som kan användas vid automatisk rangordning av rättelseförslag i ett rättstavningsprogram.

Svar

Förfinad metrik
Alla ord på editeringsavstånd ett (t ex her - hyr) är förstås närmare än ord på editeringsavstånd två (t ex her - term), men vissa ord på avstånd ett är troligare än andra. Exempel:
  • enkel/dubbelskrivning av konsonant (her - herr)
  • byte av ljudnära bokstäver som e och ä (her - här) eller g och j (jer - ger)
  • byte av närliggande bokstäver på tangentbordet som r och t (her - het)
Ordfrekvenser
Föreslå ord som i vanligare i språket före ord som är ovanligare. Vanliga ord som kan felstavas som her är till exempel har, här och hur.
I ett rättstavningsprogram utnyttjar man lämpligen båda metoderna och viktar ihop resultatet.

Uppsatsuppgift

Programmet Stava har suffixregler som gör att alla böjningsformer inte behöver finnas i ordlistan. Däremot saknas det för närvarande regler för fogemorfem. Man skulle till exempel vilja ha en regel som säger att om ordet xxx-ing finns i ordlistan så ska xxx-ings vara ett tillåtet förled i sammansättningar. Skapa ett antal lämpliga fogemorfemsregler, och försök få en uppfattning om ungefär hur stor del av förleden man kan täcka in med dessa generella regler och hur stor del man måste specialbehandla (alltså stoppa in i förledsordlistan).

Copyright © Sidansvarig: Viggo Kann <viggo@nada.kth.se>
Uppdaterad 2011-08-18