Matematické Fórum

Lukee · 10. 04. 2010 23:20

Potřebuji řešit následující problém: mám na vstupu n písmen (jen malá písmena anglické abecedy, žádné mezery ani nic jiného; n není nijak velké, zhruba do 40) a potřebuji tato písmena přeskládat tak, abych dostal nějakou větu složenou z reálných slov (věta v tomto případě není nic jiného než posloupnost slov, žádný hlubší smysl v tom není). K dispozici mám prakticky jakékoliv informace, které si můžu předtím nějak vygenerovat, například seznam všech českých slov nebo která písmena jsou často vedle jakých písmen apod. Příklad:

VratVetu("oeagseselueevpaltpoikrnmtrliiljcj")
-> "logaritmus je nejlepsi pritel cloveka" (pořadí slov už samozřejmě není důležité)

Existuje nějaký známý a popsaný algoritmus, který toto alespoň trochu efektivně řeší? Napadají mne zatím samé neefektivní overkilly, které nemohu v praxi kvůli pomalosti využít. Výsledek bych potřeboval v řádu sekund na průměrném počítači.

septolet

O zadnem algoritmu, ktery to resi nevim, kazdopadne me neco napadlo, tak to napisu, treba to bude vhodne.

Napadlo me si vytvorit takovou jednoduchou hash tabulku. Hash tabulka by byla velka podle toho, jake vsechny znaky (rozsah znaku) mas na vstupu, takze pokud mas na vstupu pismena a-z, tak by hash tabulka mela velikost 26, pro kazdy znak. Pak by si linearne prosel vstup a pro kazde pismenko by si zvysil hodnotu na danem indexu v te hash tabulce - priklad: na vstupu narazis na a, tak zvysis hash[0] o jedna. A pak opacnym zpusobem hledas slova - tz. mas nejaky seznam platnych slov, ctes je po pismenkach a zase v tom hash poli odcitas na danych indexech - tady bys akorat jeste musel resit to, ze pokud nejake slovo na ruznych indexech zmeni hash pole a pak zjistime, ze toto slovo ze vstupu neslozime (tedy nejaky index v hash poli ma hodnotu 0), tak se to hash pole zase musi vratit do stavu, v kterem bylo nez jsme s timto slovem zacali pracovat. Pokud by nejaky index (tedy nejake pismenko) v tom hash poli melo hodnotu 0, tak bys mohl vyradit vsechna slova, ktera toto pismenko obsahuji.

Pravdepodobne to nebude nic extra, ale vstupni retezec bys pri pouziti tohodle cetl jen jednou, takze n krat. To same pak se slovy ze slovniku, tam bys cetl tolikrat, kolik pismen maji vsechna slova, spise ani ne, pokud bys odfiltroval slova, ktera uz urcite nenajdes (viz. "Pokud by nejaky index (tedy nejake pismenko) v tom hash poli melo hodnotu 0, tak bys mohl vyradit vsechna slova, ktera toto pismenko obsahuji.").

Takhle bych se to nejspis pokusil resit ja, nadruhou stranu nejspis bude existovat daleko efektivnejsi reseni.

Lumikodlak · 06. 11. 2010 15:10

Je tohle stale otevrene? Zdalo se mi to zajimave, tak jsem to zkusil naprogramovat. Pri pouziti anglickeho slovniku s 850 slovy pro tu vetu "oeagseselueevpaltpoikrnmtrliiljcj" trvalo necelych 20 minut najit vsech 5013 reseni, jestli staci najit jakekoliv reseni, tak je to ani ne na vterinu. Napadaji me moznosti, jak to zrychlit, ale nevim, jestli ma cenu to resit.

(ukazky reseni pro tu vetu "oeagseselueevpaltpoikrnmtrliiljcj" :
"a cake ever girl ill join jump let so step"
"join jump let level pig rail rat see sock"
"as grip ice join jump level or steel talk")

Lukee · 06. 11. 2010 15:16

↑ Lumikodlak:
Otevřené to asi je, ale řešení už znát nepotřebuji :-).

Matematické Fórum

#1 10. 04. 2010 23:20

Rozpoznání slov z rozházených písmen

#2 11. 04. 2010 00:27 — Editoval septolet (11. 04. 2010 03:33)

Re: Rozpoznání slov z rozházených písmen

#3 06. 11. 2010 15:10

Re: Rozpoznání slov z rozházených písmen

#4 06. 11. 2010 15:16

Re: Rozpoznání slov z rozházených písmen

Zápatí