[ri4pp:2006] - Re: Morganov algoritam by "Jovan Popovic" <jovan@etf.bg.ac.yu>

Morganov algoritam ili spelling repair funkcija pokusava ili da zameni
mesta za dva uzastopna karaktera ili da obrize jedan karakter. Na pimer za
10010 i 10100 zamena moze da se izvrsi posto kada 3 i 4 karakter zamene
mesta dobija se druga rec. Ostali karakteri MORAJU buti identicni. Na
primer:

1   0   0  1   0
|   |    \/    |
|   |    /\    |
1   0   1  0   0

Drugi nachin popravke je da se ukloni jedan karakter iz duze reci i da se
proveri da li su reci identicne. Na primer za 10010 i 1000 kada se ukloni
[1] na poziciji 4 dobijaju se identicne reci 1000 i 100[1]0:

1  0  0 [1]  0
|  |  |     /
|  |  |    /
1  0  0  0

Pozdrav,
Jovan




>
> On 9/6/06, Jovan Popovic <jovan@etf.bg.ac.yu> wrote:
>>
>> Pogledajte u zbirci ili u vezbama onaj zadatak sa funkcijom
>> spelling-repair to je morganov algoritam.
>>
>> Pozdrav,
>> Jovan
>>
>>
>>
> U tom zadatku sa Spelling_repair funkcijom pise :
>
> 2.c  s[0:i-1] == t[0:i-1], s[i+1:end] == t[i+1:end], s[i] == t[i+1] i
> s[i+1] == t[i] vrati true.  Ovo sigurno ne treba ovako i ja cu
> pretpostaviti da treba ovako :
>
> s[0:i-1] == t[0:i-1], s[i+2:end] == t[i+2:end], s[i] == t[i+1] i
> s[i+1] == t[i] vrati true.
>
> Ako sam dobro pretpostavio, onda resenje 4. zadatka nije dobro jer se
> 10010 moze zameniti sa 10100, a ne 10101
>
> u slucaju 10101, 3. i 4. pozicija su zamenili mesta, ali je 5.
> pozicija razlicita (pravilo 2.c), pa se vraca false
>
> u slucaju 10100, 3. i 4. pozicija su zamenili mesta i 5. pozicija je
> ista (pravilo 2.c), pa se vraca true
>
> Jesam li ja ovo dobro pokapirao?
>
>
>
> -----------------------------------------------------------------
> unsubscribe:
>    minimalist@rti.etf.bg.ac.yu?subject=unsubscribe%20ri4pp
> -----------------------------------------------------------------
>