Atstumas tarp žodžių
Taškai: 9
Atstumas tarp dviejų žodžių matuojamas operacijų, kuriomis vienas žodis keičiamas į kitą, skaičiumi. Ženklų eilutės keitimas žodžiu atliekamas trimis operacijomis:
- įterpti vieną ženklą į bet kurią eilutės vietą,
- pašalinti bet kurį vieną ženklą iš eilutės,
- pakeisti bet kurį eilutės ženklą kitu ženklu.
Tada Levenšteino atstumas tarp dviejų eilučių yra mažiausias skaičius čia aprašytų operacijų, kurias atlikus iš vienos eilutės gaunama kita eilutė. Pavyzdžiui, atstumas tarp eilučių „akmuo“ ir „piemuo“ yra 3, nes reikia 3 operacijų:
1) akmuo → pkmuo (a keičiama į p),
2) pkmuo → pimuo (k keičiama į i),
3) pimuo → piemuo (įterpiama e).
Mažiausias atstumas tarp žodžių yra lygus 0 tuo atveju, kai žodžiai sutampa. Kuo atstumas didesnis, tuo žodžiai labiau skiriasi.
Koks atstumų tarp žodžių vidurkis:
1. patranka – palaima
2. observatorija – konservatorija
Įrašyk skaičių.
Atstumo sąvoka reikalinga rašybos tikrinimo ir koregavimo programose, taip pat kituose tekstų apdorojimo algoritmuose. Ši funkcija taip pat naudojama kompiuterinėje lingvistikoje, kai matuojami atstumai tarp atskirų žodžių aibių. Žinomos ir kitos žodžių atstumų metrikos, kai naudojami kitokie keitimo operacijų rinkiniai, pvz., LCS, Hemingo, Jaro–Vinklerio metrikos. Analogiški metodai naudojami ir genetikoje, tiriant DNR grandinių panašumus.
Atkreipkite dėmesį, kad protmūšių žodžių grandinėles sudarančių gretimų žodžių Levenšteino funkcija yra lygi 1.
Plačiau apie tai galima paskaityti čia
https://lt.wikipedia.org/wiki/Levenšteino_atstumas
Raktiniai žodžiai: Levenšteino atstumas, ženklų eilutė, ženklas.
Teisingas atsakymas yra 3.
Pirmos žodžių poros atstumas yra 4, nes trumpiausias keitimas yra toks:
- patranka – palranka – palanka – palaika – palaima
Antros žodžių poros atstumas yra 2, nes trumpiausias keitimas yra toks:
- observatorija – kobservatorija – konservatorija
Taigi abiejų žodžių porų atstumų vidurkis yra 3.