2014 2015 2016 2017 2018
BEBRO konkurso užduotys 2017

 

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ų.

Paaiškinimas

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.

Atsakymas

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.

Interaktyvi užduotis