Laitan tänne, kun en jaksa miettiä. ;)
Mitkä kirjaimet pitäisi valita aakkospalikoihin (kuution sivuille), jotta palikoilla voisi kirjoittaa mahdollisimman monta eri sanaa tietystä sanastosta?
Mikä edes olisi paras tapa tarkastaa, mitkä sanat palikoista saa tehtyä? Ahne algoritmi ei saa aina sanoja tehtyä, esimerkiksi palikoista AB ja AC ei ahneesti saa sanaa AB, koska AB-palikasta käytetään A-kirjain ja B-kirjainta ei sitten enää ole). Kaikkia eri järjestyksiä ei tietenkään ehdi kokeilla.
Oma ensisijainen tavoitteeni olisi suunnitella noin 12 palikkaa, joista voisi tehdä yleisimpiä suomen kielen sanoja. Tähän mennessä päädyin rajaamaan aakkostoa niin, että käytössä ovat ASCII-merkit a-z sekä ä, ö ja viiva. Pienten tekstauskirjainten kyseessä ollessa voin myös hyödyntää kirjainten symmetriaa niin, että b=q, d=p ja n=u (ja tarvittaessa l=-). Sanaston pohjana on kotus-sanalista-v1, joka vastaa tekemäni karsinnan myötä enimmäkseen Putkapostien sanalistaa.
Toteutin tuon ahneen algoritmin edellä mainitusta puutteesta huolimatta. Kerään sanalistasta enintään tietyn mittaiset uniikit anagrammit niin, että harvinaiset kirjaimet tulevat ensimmäisiksi, jolloin loogisesti ahneen algoritmin ongelmat vähenevät. Käyn anagrammeja läpi satunnaisessa järjestyksessä ja ahneesti lisään puuttuvat merkit palikoihin. Kohtuullisen pienellä toistomäärällä algoritmi saavuttaa (ahneella tarkastuksella katsottuna) 7–10 kirjaimen ylärajalla 99–96 % sanastosta.
Tietysti olisi mahtavaa, jos saisi huomioitua myös taivutusmuodot ja useamman sanan fraasit. Minulla ei ole tähän kovin hyvää valmista lähdettä, mutta Raamattu löytyy sattumalta tekstitiedostona. Kun siitä ottaa sanat ja kahden peräkkäisen sanan yhdistelmät ja rajaa nämä enintään 10 merkkiin, jälleen 97 %:n ratkaisu löytyy.
Tuleeko hyviä ideoita tehtävään? Toki tuo saavutettu tulos on jo aika hyvä, mutta tietysti prosentit laskevat, mitä lähempänä sanan pituus on palikoiden määrää, eli optimoinnille on varmasti varaa.
Metabolix kirjoitti:
Laitan tänne, kun en jaksa miettiä. ;)
Olisit laittanut putkapostiksi niin ei olis tarvinnut myöntää mitään. :D
Metabolix kirjoitti:
Mikä edes olisi paras tapa tarkastaa, mitkä sanat palikoista saa tehtyä?
On 924 tapaa valita 12 palikasta 6. Jokaiselle kuuden palikan ryhmälle on mahdollista generoida kaikki anagrammit: 924 * 6^6 = n. 43 miljoonaa.
Kun halutaan muodostaa annettu 12-merkkinen sana palikoista, käydään kaikki 924 kombinaatiota läpi ja tehdään 2 lookuppia.
Toki palikoista joihin kirjaimet on jo valittu on helppo selvittää mitkä sanat niistä saadaan muodostettua.
Metabolixin kysymys koski nähdäkseni sitä, miten valita parhaat kirjaimet 12 palikkaan (kussakin 6 sivua). 24 merkin (28 - 4) joukolla saa tehtyä suuruusluokkaa 10^95 erilaista yhdistelmää. Tuollaisen määrän läpikäyminen ei niin vain loopissa onnistu.
Palikoiden suunnittelu on astetta vaikeampi ongelma juu.
Ainakin on helppoa osoittaa, että täydellistä ratkaisua ei ole olemassa. Kotuksen sanalistasta ei voi muodostaa edes kaikkia perusmuotoisia 12-kirjaimisia sanoja.
Käytössä on 6*12 = 72 kirjainta.
Tarvitaan vähintään 6 A-kirjainta, jotta saadaan "raakamakkara".
Tarvitaan vähintään 5 I-kirjainta, jotta saadaan "riippuliidin".
Tarvitaan vähintään 5 U-kirjainta, jotta saadaan "suurisuisuus".
Ja niin edelleen, en edes käynyt kaikkia kirjaimia läpi ennen kuin 72 ylittyi.
Lisäys: Jakaisin ongelman varmaan kahteen vaiheeseen. Valitaan ensin, miten monta kappaletta kutakin kirjainta käytetään (tämän voi tehdä vaikka käsin). Sitten karsitaan sanalistasta pois mahdottomat sanat. Voi olla, että tätäkään ei voi ratkaista optimaalisesti, mutta tuntuu helpommalta miettiä fiksatun kirjainlistan jakamista palikoihin kuin koko ongelmaa kerralla.
Grez kirjoitti:
Olisit laittanut putkapostiksi
Pahus sentään! Mutta posteihin lähetetään vain tuloksia, joten en saisi sieltä omaan käyttöön muokattavaa ratkaisuideaa. Yhden palikkasarjan tietysti saisin.
jlaire kirjoitti:
Ainakin on helppoa osoittaa, että täydellistä ratkaisua ei ole olemassa.
Tämä on aivan odotettavissa. 72 kirjaimen tarve ylittyy jo 1–7-merkkisissä sanoissa aakkosrajauksella a-zäö.
jlaire kirjoitti:
Kun halutaan muodostaa annettu 12-merkkinen sana palikoista, käydään kaikki 924 kombinaatiota läpi ja tehdään 2 lookuppia.
Sanoissa voi olla (ja usein olisi) vähemmän kuin 12 palikkaa, joten tuota hakua täytyy hieman muokata, mutta sama idea varmaan toimii. Jokin kikka olisi silti tarpeen, jotta tuota voisi päivittää nopeasti myös palikoiden generoinnin aikana.
jlaire kirjoitti:
Jakaisin ongelman varmaan kahteen vaiheeseen. Valitaan ensin, miten monta kappaletta kutakin kirjainta käytetään (tämän voi tehdä vaikka käsin). Sitten karsitaan sanalistasta pois mahdottomat sanat. Voi olla, että tätäkään ei voi ratkaista optimaalisesti, mutta tuntuu helpommalta miettiä fiksatun kirjainlistan jakamista palikoihin kuin koko ongelmaa kerralla.
Ei tuosta nyt ainakaan suoraa läpimurtoa saa, koska pelkkä kirjainmäärä ei vielä paljasta ”mahdottomia” sanoja. Jos sanalistan jokainen sana sisältäisi kuusi A-kirjainta, naiivi ratkaisu jättäisi näistä A-kuutioista 6×5 sivua käyttämättä ja fiksumpi ratkaisu uhraisi muistakin kuutioista yhden sivun A-kirjaimelle, jotta alkuperäisten A-kuutioiden muut sivut voisi hyödyntää eri kirjaimille.
Metabolix kirjoitti:
Sanoissa voi olla (ja usein olisi) vähemmän kuin 12 palikkaa, joten tuota hakua täytyy hieman muokata, mutta sama idea varmaan toimii.
Yksi tapa olisi lisätä joka kuutiolle seitsemäs sivu joka on jokin erikoismerkki jota ei esiinny sanoissa, vaikka '$'. Lyhyistä sanoista voi tehdä 12-merkkisiä lisäämällä loppuun dollareita.
Metabolix kirjoitti:
Jos sanalistan jokainen sana sisältäisi kuusi A-kirjainta, naiivi ratkaisu jättäisi näistä A-kuutioista 6×5 sivua käyttämättä ja fiksumpi ratkaisu uhraisi muistakin kuutioista yhden sivun A-kirjaimelle, jotta alkuperäisten A-kuutioiden muut sivut voisi hyödyntää eri kirjaimille.
Ihan totta, mutta tällaisia tapauksia ei välttämättä tule vastaan realistisen sanalistan kanssa.
Tässähän muuten tehtävä oikealla sanalistalla yllättäen helpottuu, kun palikkojen määrää lisää (vaikka samalla pidentäisi sanoja vastaavasti), joten taidan päätyä IRL-ratkaisuun, jossa teen peräti 20 palikkaa. Näillä saa heittämällä 20-merkkisistä Kotuksen sanoista 99,3 % ja 18-merkkisistä Raamatun sanoista ja sanapareista 99,6 % katettua, tai sitten koodissani on jokin bugi.
Päädyin ratkaisemaan ongelman lähes alkuperäisellä menetelmälläni mutta lisäyksittäin, eli ratkaisin ensin pienempää palikkamäärää lyhyemmille sanoille ja pidin kyseiset palikat myöhemmillä kierroksilla muuttumattomina. Tästä on se lisähyöty, että saman ratkaisun alkuosaa voi suoraan käyttää pienemmille palikkamäärille (ts. lyhyitä sanoja tehdessä tietää, mitkä palikat yleensä riittävät). En käyttänyt jlaireen muistisyöppöä tarkastusideaa vaan yksinkertaisesti lisäsin ahneeseen tarkastukseen satunnaisia permutaatioita, jolloin luotettavuus parani selvästi.
Käytin optimoinnissa näitä portaita (pituus/palikoita): 5/7, 6/9, 10/12, 13/15, 19/19 ja lopuksi 7/20 lyhyisiin sanoihin tarpeellisten harvinaisten merkkien takia. Viimeiseen palikkaan tuli tästä vain neljä kirjainta (cwxz), joten lisäsin siihen puuttuvien 12-merkkisten sanojen perusteella vielä kirjaimet o ja y.
Palikat ovat: fhjmyä, klprsv, klpstä, aeimoä, aeinot, ailnrö, bghnsy, ajkmnt, ceivyö, abehlp, einost, agnrtä, aimnsä, ailnoä, fklnty, aeknpz, aijntv, ainrst, aeilnö, cowxyz.
Lopputulos kattaa Kotus-sanastosta lähes kaikki 7-merkkiset sanat (puuttuu www ja wigwam, en jää kaipaamaan), 99,98 % 12-merkkisistä, 99,97 % 16-merkkisistä ja 99,71 % 20-merkkisistä. Puuttuvista sanoista moni sisältää erityisen monta jotain harvinaista kirjainta (esim. lobbybaari, leggingsit, www-vastaava). Käyttökelpoisina osaratkaisuina 6/9 kattaa 98,2 %, 10/12 kattaa 98,9 % ja 13/15 kattaa 99,6 %.
Tuli tuollainen mileen, kun luin ratkaisusi, että ei mitenkään olisi mahdollista tehostaa algoritmiä, kun jos poissulkee yhdyssanat, ja ajatellaan kotus-sanastoa, jossa on perusmuodossa sanat, niin yleensä ei a-ä, o-ö, tai u-y a-å esiinny samoissa sanoissa, kun tuossa näyttäisi aika monessa olevan sellaiset kirjainyhdistelmän palikoissa, a-ä -lukuunottamatta, jos o-ö, u-y ja a-å, no ruotsalaista aakea nyt missään näyttänytkään olevan, mutta jos yksi kirjain kustakin on kerrallaan käytössä, ja yhden käyttö poissulkee muut.
En muista, mitä itsekin tuota kotuksen suomen kielen sanalistaa joskus tutkinut, onko siellä yhdyssanoja, kuten "aamuyö", "työuuras", no sitä ei taida olla siellä vaikka olisi suomen kielen sana, perinteisissä kuvaristikoissa tainnut joskus esiintyä, mutta jos ei yhdyssanoja ja ruotsalaista aakea oteta huomioon, minkälaisia tuloksia voisit viilata, jos pistät samoihin palikoihin nuo a-ä, o-ö, u-y -yhdistelmät.
Jere Sumell kirjoitti:
jos poissulkee yhdyssanat
Se ei taas vastaa omaa tavoitettani, koska lyhyitä ja yleisessä käytössä olevia yhdyssanoja on niin paljon.
Jere Sumell kirjoitti:
yleensä ei a-ä, o-ö, tai u-y a-å esiinny samoissa sanoissa, – – minkälaisia tuloksia voisit viilata, jos pistät samoihin palikoihin nuo a-ä, o-ö, u-y -yhdistelmät.
En saa ihan selvää, mitä yrität ehdottaa algoritmin kannalta. Joka tapauksessa näiden poissulkevien kirjainten huomiointi erikseen ei luultavasti auta mitään, koska asia tulee jo käsiteltyä sen kautta, mitä palikoita on vapaana uusilla kirjaimilla täydennettäviksi. Jos ä-kirjain puuttuu, luultavasti jokin a-palikka on vapaana ja nämä helpommin päätyvät siis samaan palikkaan. Tuossahan on 4 kpl a-ä-palikoita.
Johtopäätöksesi tietyistä kirjainpareista on melko puuttellinen, koska sama pätee muihinkin etu- ja takavokaalin yhdistelmiin (kuten a-ö, a-y, o-ä). Toisaalta näitä esiintyy lainasanoissa (”pyjama”, ”dynamo”) ja varsin yleisissä yhdyssanoissa (”työmaa”, ”yöjuna”).
Jere Sumell kirjoitti:
a-å, no ruotsalaista aakea nyt missään näyttänytkään olevan,
Ei liene yllätys, että suomen kielen sanalistassa å-kirjainta ei juuri esiinny... Ainoa sana on itse asiassa ångström (mittayksikkö, Å = 0,1 nm). Mutta jos kuitenkin å olisi suomessa käytössä, miksi a-å olisi poissulkeva pari, kun å on kuitenkin äänteellisesti o ja sopii a:n kanssa aivan hyvin?
Ei itselläni mitään aikomusta ollutkaan puuttua tuohon kehittämäsi ratkaisun tehokkuuden parantamiseen, kun et edes julkaissut mitään koodia, tai vaikka olisit julkaissutkin, ei sitenkään varmaan. Varmaan ihan mallikelpoisesti olet oikein tuon tajunnut.
Erisnimissähän voi olla å ja a sama, ja jossain firmojen toiminimi-määritelmissä.
"Latasin joskus hitaalla modeemilla Mikrobitin MBNet -purkkiin soitettuani lehden palstalla esitellyn uutuuspelin "Invataxi".
"Minäkin pelasin sitä. Aloin sen jälkeen seuraamaan Åkesoftia", joka ilmoitettiin kyseisen pelin pelikehittäjäksi
Toisaalta en tiedä sukunimissä, jos å ei ole saatavilla, varmaan ihan suomen kielen kieliopin mukaan "aa" -korvaavana menee täysin läpi.
Ainakin posti luultavasti tulee perille, kun itselläni on vedonlyönti-tili Bet365:llä, joka lähetti silloin kun rekisteröin tilini, niin kotiosoitevahvistus-pin-koodin paperipostitse, ja olin ilmoittanut ä-kirjaimen osoitteessani ae-yhdistelmänä, ja posti tuli ajallaan oikeaan osoitteeseen täällä Suomessa
On totta, että ruotsalainen å on aika turha meidän hienossa suomen kielessämme. En tiedä sitten, jos pakkoruotsin tuputus kielletään lailla, joskaan sitä ei enää taritse kirjoittaa pakollisena ainakaan kaikissa lukioissa, mutta kotikaupunkini Turussa se on jos hakee julkista työpaikkaa kaupungilta, kielivaatimuksena, kun tämä on kaksikielinen kunta, vaikka täällä on suhteessa suomea puhuviin todella vähän ruotsinkielisiä, ja venäjää ja arabiaakin puhuvia taitaa olla enemmän jo nykisin. Sekin ihmetyttää, kun AMK-opinnoissakin ja alemman korkeakoulututkinnon läpäisyvaatimuksena on säädetty laissa yliopistossakin opiskelleiden keskuudessa tuo virkamiesruotsin hallinta.
No, ei mennä kielipolitiikkaan, vaan pysytään tässä aiheessa on pakkoruotsista Suomessa mitä mieltä tahansa, ei vielä lähdetä vaatimaan barrikaadeilla aakkostomme osalta å:n poistamista hamaan ihmisen elossa olemisen loppuun saakka.
Aihe on jo aika vanha, joten et voi enää vastata siihen.