Autor Zpráva
Martin02
Profil
Ahoj,

ne že bych to na něco potřeboval, ale moc by mě zajímalo, jak to udělat. Strávil jsem už dlouho času přemýšlení o tom, ale asi mi není souzeno na to přijít.

Je to jednoduché - máte normální morseovku, akorát tam nejsou oddělovače písmen. Takže máte např. ".-....---.---" - to je "ahoj", ale taky spousta dalších věcí, neb tam nejsou ty oddělovače. Chtěl bych napsat program, co mi vypíše všechny možnosti. Převod čárek a teček do písmen už bude trivialita.

Nechci celý kód, jen spíše nastínit, jak na to, neb já vůbec nemám tušení.


Děkuji
Tori
Profil
To vypadá jako takové rozvětvující se možnosti - mám řetězec, projdu písmena morseovky a najdu všechny shody od začátku, ukládám si nalezený znak + zbytek řetězce. Při další iteraci stejným způsobem projdu všechny ty zbylé řetězce, zase najdu shody, přidám nový znak k minulému a uložím zbytek řetězce. Na první pohled to vypadá jako vnořená pole, ale šlo by to asi i jako dlourozměrné pole: po první iteraci budu mít např. (do morseovky dávám nesmysly, neumím ji):

0 => [ "a", "-.---" ]
1 => [ "b", "---" ]
. Po další iteraci z toho vytvořím nové pole:
0 => [ "ac", "--" ]
1 => [ "aa", ".---" ]
2 => [ "bo", "" ] -- tohle se při příští iteraci jen zkopíruje do nového pole. K ostatním se dál dohledají další možnosti.
3 => [ "bm", "-" ]
Ale je to jen první nápad. Dost pravděpodobně existuje efektivnější algoritmus.
juriad
Profil
Už na tom pracuju, lze najít všechny možnosti v čase O(délka vstupu + délka výstupu).
Založené je to na dynamickém programování.


http://kod.djpw.cz/ombb
Zkus zadat třeba slovo test - / . / ... / - bez oddělovačů -....-.
Pozor na to, že se zvětšující se délkou roste počet možností. Pro vstup .---..-.-....--.. (juriad) je jich již 40376 a prohlížeči to již nějakou dobu trvá.


Výpočet probíhá ve dvou fázích: posměrné a protisměrné.

Napřed se do pole ends ukládají výskyty znaků, která na dané pozici končí a navazují na nějaký předchozí text.
Zkus si zadat třeba .-.- a podívej se do pole ends; snad to pochopíš.

V druhé fázi se začne procházet pole ends od konce (odpovídá konci vstupu) a hledají se možnosti pro poslední znak, z toho se odvodí, kde musel končit předchozí znak. A pak se zavolá nad zbytkem (pro pohodlnost jsem to napsal rekurzivně, ale šlo by přepsat do cyklu).
Parciální shoda (možnost) se postupně ukládá do zásobníku result; jakmile se dojde až na začátek textu, je zásobník přetransformován na text a uložen do pole results, které je konečným výstupem.
_es
Profil
Martin02:
Obávam sa, že to nemá praktický zmysel, pri dlhšom texte bude počet možných „vysvetlení“ textu astronomicky veľký. Navyše, okrem písmen sú v m. abecede aj číslice, rôzne špeciálne znaky ako otáznik, výkričník, úvodzovky,..
juriad
Profil
_es:
Má to význam, pokud by to skombinoval s nějakým slovníkem a ořezával nesmysly.
Morseova abeceda je bohužel hodně hustá: skoro každá jedno až čtyřznaková posloupnost kóduje nějaký znak.
_es
Profil
juriad:
Akosi ma nenapadá, na čo by to niekomu bolo. Kde si videl (počul) morseovku bez oddeľovačov (prestávok) medzi písmenami?

skoro každá jedno až čtyřznaková posloupnost kóduje nějaký znak.
Ak sa zarátajú aj špeciálne znaky a číslice tak jedno až šesťznaková (cs.wikipedia.org/wiki/Morseovka#K.C3.B3d_Morseovy_abecedy). Okrem toho je na wikipedii spomenutá možnosť rozšírenia o národné znaky. Jednoducho - morseovka sa skladá z postupnosti troch znakov: bodka, čiarka a medzera a nie dvoch. Odstránenie jedného z tých troch znakov, medzery, nedáva zmysel, podobne ako odstránenie bodky či čiarky z jej zápisu.
juriad
Profil
_es:
Šifrovačky; ano i tam oddělovače také jsou, ale často nejsou zrejmé. V terénu se hodí do programu hodit deset/dvacet prvních teček a čárek a koukat, jestli z toho leze něco smysluplného.

Vaše odpověď


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm: