Anagrammid ja Python I

Üks tore blogi pani mu tükiks ajaks tegelema anagrammidega.

TÜ progemise kursus andis ideid.

Tekstitöötlus on hea viis programmeerimist ja uut programmeerimiskeelt õppida.

Lahtiütlus:

Ma ei ole programmeerija! Ma ei ole õppinud ei algoritme ega andmestruktuure. Pythonit olen vaid natuke nuusutanud.

Head koodi või nupukaid lahendusi siit EI LEIA.

Õige koodineeger lahendaks samad ülesanded kordi lihtsamalt ja suurusjärk kiiremini.

Järgnev on lihtsalt... ühe mõtteharjutuse ja näputöö üleskirjutus.

Ühtlasi pole siin kusagil mingeid veakontrolle ("kas fail ikka on olemas?") jne.

Anagrammid

on sõnad, fraasid, laused, mis saadakse üksteisest tähtede ümbepaigutuse teel.

kala -- kaal

kinnisvara -- ninasarvik

kaur virunurm -- nurru kruvima

Andmed sisse!

Eesti keele lemmad on EKI failis https://www.eki.ee/tarkvara/wordlist/lemmad2013.txt.

Loen need Pythoni sõnastikku (dictionary), kus kõik samasugustest tähtedest sõnad on koos.

Anagrammide leidmise mõttes on "kala" ja "kaal" ju üks ja sama asi.

Sõnastiku võti (key) on sõna sorteeritud kuju - nimetan seda edaspidi sõna räsiks.

Sõnastiku väärtus (value) sama võtmega / sama räsiga sõnade list.

Sõna "sorteerimiseks" on pythonis veidi imelik mehhanism ''.join(sorted(sona))

Niisiis:

sonastik = dict()           

ff = open("lemmad2013.txt", "r", encoding="utf8")

for x in ff:

    sona = x.lower().strip()                      # eemaldame suurtähed ja tühikud

    if len(sona)>=sona_min_pikkus:                # jätame lühikesed sõnad lugemata, sest seal on palju lühendeid jne

        sona_rasi = ''.join(sorted(sona))         # "kala" => "aakl"

if sona_rasi in sonastik: # kui sõna on juba sõnastikus, siis lisame ta vastavale listile

            sonastik[sona_rasi].append(sona)      

        else:                                     # kui ei ole, siis alustame uut listi

            sonastik[sona_rasi] = [sona]          

ff.close()

Edasi toimetan ma kogu aeg räsidega ja ainult tulemuste välja trükkimiseks otsin sõnastikust inimkeelse vaste, või vaste nimekirja.

See lemmade nimekiri on veidi põhjalik.

Seal on paaritähelised lühendid, harvad tüved ja onomatopoeetika.

Et üldse asja saaks, tuleb kõik kuni kolmetähelised sõnad välja visata, muidu koosnevad su anagrammid ainult jamast:

kaur virunurm = ka ir mv uun urr

No ei ole ju huvitav.

Kaotatu asemele võib ise mõned lühikesed sõnad lisada, verbidest ("ma" lõpuga sõnad) oleviku ja lihtmineviku vormid lisaks teha jne.

Ühesõnalised anagrammid

Sõna sõnastikus sisaldumise kontroll on triviaalne:

>>> print (sonastik["aakl"])

['kaal', 'kala', 'laka']

Otse tavalise sõna järgi otsida ei saa - print (sonastik["kala"]) annab vea.

Sellise võtmega kirjet ju ei ole!

Küll aga töötab:

>>> print (sonastik[''.join(sorted("kala"))])

['kaal', 'kala', 'laka']

Seega on ühesõnaliste anagrammide leidmine sisuliselt tehtud:

- loeme sõnastiku sisse

- küsime anagrammitavat sõna

- trükime sõnastiku vastava kirje välja (kui on)

while(True):

    sona = input("Mille anagramme otsid? ")

    sona_rasi = ''.join(sorted(sona.lower().strip()))

    if sona_rasi in sonastik:

        print(sonastik[sona_rasi])

    else:

        print("Kahjuks ei leidnud.")

Tulemus on mõneti kole:

Mille anagramme otsid? kalad

['kadal', 'kalda']

Trükitakse välja ju list - ja kogu selle "süntaks".

Kuna meil on vaid sõnad, milles pole tühikuid jne, pole meil neid kantsulge ja apostroofe vaja.

Neist saab vabaneda regulaarvaldise / regexp abil.

import re

...

print(re.sub('[,\'\[\]]', '', str(sonastik[sona_rasi])))

Hilisemaks teeme endale "ilutrüki" funktsiooni, mis võtab sisse listi ja trükib selle välja ilma süntaksi-märgistuseta.

# prettyprint

def pp(s):

    return re.sub("[\'\[\],]", "", s)

...

print (pp(mistahes_list))

Pikad / mitmekordsed ühesõnalised anagrammid

Kaua sa ikka üksikute sõnade anagramme otsid?

Muudame ülesannet:

1) leiame kõik pikad ühesõnalised anagrammid.

2) leiame kõige anagrammi-rohkemad eesti lemmad.

Kuna meil on andmed õiges struktuuris, on need väga kerged küsimused.

Võime näiteks "sonastiku" listi pikkuse järgi ära sorteerida.

sorted() meetodile saab ette anda, mille järgi sorteerida - kas võtme pikkuse või väärtuse pikkuse järgi.

Väärtus on meil anagrammide list, mille pikkus tähendabki seda, mitu anagrammi-variantide sellest sõnast on.

Google "python dictionary sort by value length" ütleb:

>>> kkk = sorted(sonastik, key=lambda k: len(sonastik[k]), reverse=True)

Nüüd on "kkk" list sõnadest nende anagrammide arvu järgi.

Me saame neid ja neile vastavaid anagrammi-liste leida nii:

>>> print (kkk[0])

aikmstu

>>> print (kkk[0], sonastik[kkk[0]])

aikmstu ['kitsuma', 'kutsima', 'mustika', 'mutikas', 'sitkuma', 'tiksuma', 'timukas', 'tuiskam', 'tuksima']

>>> print (kkk[1], sonastik[kkk[1]])

akstu ['aktus', 'katsu', 'katus', 'kaust', 'kutsa', 'skaut', 'stuka', 'takus', 'tasku']

Teine variant on pythoni "list comprehension", mis teeb lennult uue, etteantud tingimustega listi.

Küsime kasutajalt sõna miinimum-pikkust ja anagrammide miinimum-arvu ja otsime vastavaid sõnu.

"Otsime" on muidugi liialdus, python lihtsalt koostab meile neile vastava listi.

Vastav rida on rasvases kirjas:

nn = input("Kui pikki anagramme otsid? ")

cc = input("Kui mitme kordusega? ")

xx = [x for x in sonastik if len(x) > int(nn) and len(sonastik[x]) >= int(cc)]

for x in xx:

print(x, "--", re.sub('[,\'\[\]]', '', str(sonastik[x])))

Kui pikki anagramme otsid? 12

Kui mitme kordusega? 3

aadeeijmnnstu -- teadmisjanune teenindusjaam teenindusmaja

aaaadeiioprrt -- patareiraadio raadiopatarei radioteraapia

Lihtne, eks!!!!

Suurte andmemahtude korral ei ole need algoritmid head.

Tehakse palju uusi liste, käiakse kogu sõnastik alati üle jne.

Alternatiivsed lahendusi on palju.

Võib nt kasutada pythoni Counter() struktuuri, mis on ekstra mõeldud asjade loendamiseks.

Teises osas tegeleme kaheosaliste anagrammidega.

Kogu programm

# Anagrammide leidmine

#

# Leiab sõna otsesed anagrammid

# 

# sõnade allikaks https://www.eki.ee/tarkvara/wordlist/lemmad2013.txt

# avab fail, arvestab UTF formaadiga

# testimiseks võib kasutada readlines(10000), mis piirab loetava faili ~10000 baidiga

import re

sona_min_pikkus = 4

sonastik = dict()

ff = open("lemmad2013.txt", "r", encoding="utf8")

for x in ff:

    sona = x.lower().strip()

    if len(sona)<sona_min_pikkus:

        continue

    sona_rasi = ''.join(sorted(sona))

    if sona_rasi in sonastik:

        sonastik[sona_rasi].append(sona)

    else:

        sonastik[sona_rasi] = [sona]

ff.close()

while(True):

    sona = input("Mille anagramme otsid? ")

    sona_rasi = ''.join(sorted(sona.lower().strip()))

    if sona_rasi in sonastik:

        print(re.sub('[,\'\[\]]', '', str(sonastik[sona_rasi])))

    else:

        print("Kahjuks ei leidnud.")