Hollosi Information eXchange /HIX/
HIX CODER 112
Copyright (C) HIX
1998-05-20
Új cikk beküldése (a cikk tartalma az író felelőssége)
Megrendelés Lemondás
1 Re: A Do:mo:lki algoritmus (mind)  151 sor     (cikkei)
2 Re: Ujra: bitsorozatba bitsorozat kereses (mind)  26 sor     (cikkei)
3 Grafikus kepallomany pascal hatterkent (mind)  5 sor     (cikkei)
4 [DOS] int 21 ReadLN (mind)  26 sor     (cikkei)
5 Re: Ujra: bitsorozatba bitsorozat kereses (mind)  11 sor     (cikkei)
6 VISUAL BASIC 100% CPU (mind)  4 sor     (cikkei)
7 WinWord header ? (mind)  14 sor     (cikkei)

+ - Re: A Do:mo:lki algoritmus (mind) VÁLASZ  Feladó: (cikkei)

On 18 May 98 at 14:20,  > wrote:

> Elore magadott sztringeket keresunk egy input karaktersorozatban. Most
> eppen az "abc"-t es a "bcde" -t. Csinalunk harom bitvektort ( S, E, U ),
> meg egy bitmatrixot ( M ) az alabbi tartalommal:
[...stb...]

Aha!

Dömölki Bálint-ot ismerem (egy idoben a fonokom volt), de nem tudtam,
hogy ez az algoritmus róla van elnevezve. En ezt Shift-search (vagy
shift-and) algoritmusnak ismertem. A Byte magazin illetve az MSJ irt
rola 5-6 eve, de kicsit bele kellett nyulnom, mert (szerintem) rossz
volt a programjuk :)

Kicsit egyszerubben es gyakorlatiasabban is meg lehet fogalmazni, ha
nem akarunk egyszerre tobb dolgot keresni, hanem csak egyetlent:
Tegyuk fel, hogy max 32 betu hosszusagu stringet akarunk keresni:
ekkor a keresest vegezhetjuk egy 32 bites hosszu (tehat egyetlen
regiszterben elfero) keresovektorral. Fel kell epiteni egy 256 elemu,
elemenkent 32 bites Characteristic Vector Table-t (CV tabla), ez itt
a neve a Domolki fele M matrixnak. Ebben a tablazatban minden
betuhoz azokban a bitekben van 1-es, amilyen poziciokban elofordulhat
az adott betu. A keresovektorban (regiszterben) azokon a
bitpoziciokon lesz 1-es, ameddig mar egyezett a keresett string.
Amikor elovesszuk a kovetkezo byte-ot, akkor egyreszt shift-elunk
egyet a keresovektorral, es lemaszkoljuk a CV tabla byte-adik
elemevel, hogy kideruljon, folytatodik-e ezzel a byte-tal valamelyik
eddigi substring. Ezen kivul hozza-or-oljuk a CV tabla byte-adik
elemenek elso bitjet, mert hatha indul ezzel a byte-tal uj substring.
Ha egy bit el tud erni a keresett string hosszaig, akkor talaltunk
egy egyezest.

Maga a program olyan rovid, hogy idemasolom. A programom 16
bites, DOS ala irtam, de legalabb 386-os proci kell hozza, mert
hasznal 32 bites regisztert is. Konnyen lehet belole 32 bites flat
mod-ut is csinalni. Elol all az a rutin, ami egy stringhez
megcsinalja a CV tablat, majd maga a kereses:

BuildCVTable proc far
; DS:SI= keresendo string
;    CX= string hossza = 1..32 (nincs ellenorzes)
; ES:DI= CV Table (Characteristic Vector Table) 256*4byte hosszu

; ES:DI es CX nem romlanak (At kell oket adni ShiftSearch szamara is)

; a CV tablaban minden kodhoz (0..255) egy 32bites bejegyzes tartozik
; ami leirja, hogy a keresendo stringben melyik poziciokon fordulhat
; elo a kod
        push    cx
        push    di
        cld
        xor     ax,ax
        mov     cx,256*4/2
      rep stosw
        pop     di
        pop     cx

        push    cx
        mov     edx,80000000h
bcvt1:
        xor     bh,bh
        mov     bl,[si]
        inc     si
        shl     bx,2
        or      es:[di+bx],edx
        shr     edx,1
        loop    bcvt1
        pop     cx

        ret
BuildCVTable endp

; Shift-AND algoritmus (Udi Manber & Sun Wu) Byte 1992 nov.
; Exact Match
ShiftSearch proc far
; DS:SI= szoveg, amiben keresni kell
;    BX= szoveg hossza
; ES:DI= CVTable                        (BuildCVTable =in=out)
;    CX= keresendo string hossza 1..32  (BuildCVTable =in=out)
;
; ki    CY= nc, ha talalt
;    DS:SI= a talalt szoveg moge mutat
;
        xor     edx,edx
        stc
        rcr     edx,cl        ; leallunk ilyen hossz utan
;                                                      '93 april Q&A
;;;;;;; mov     ecx,80000000h ; egyezo string hossza   MSJ szerint!
        xor     ecx,ecx       ; egyezo string hossza   szerintem

        test    bx,bx
        jz      fstV    ; ures stringben kellene keresni?
        xor     eax,eax
        movzx   edi,di
fstS:                   ; ciklus
        lodsb

; elozo sub-stringek novekszenek tovabb, ha lehet:
;               (ecx >> 1) and cv
; valamint kezdodhet egy 1 hosszusagu sub-string:
;             or (80000000 and cv)
;
        stc     ; 80000000 lesz. Kezdodhet pl. itt egy match
        rcr     ecx,1          ; es folytatodhat egy megkezdett match
        and     ecx,es:[edi+4*eax] ; ez a betu lehet-e
                                   ; ez(ek)en a hely(ek)en
        test    ecx,edx
        jnz     fstFound        ; teljes hosszusagban jo volt!

        dec     bx
        jnz     fstS
fstV:
        stc
        ret
fstFound:
        clc
        ret
ShiftSearch endp

Az algoritmus elonye nem a gyorsasaga (ennel van sokkal gyorsabb
string kereso), hanem az, hogy csupan a CV tabla modositasaval lehet
vele 'joker'-es keresest csinalni, tehat olyat, hogy pl. a string
valamelyik betuje barmi lehet, illetve pl. barmilyen nagybetu, vagy
barmilyen szamjegy, stb. Egyszeruen minden olyan byte-hoz
engedelyezni kell az adott pozicio bitjet is a CV tablaban. Persze
ehhez masmilyen BuildCVTable rutint kell irni, ha mondjuk ilyen
regular expression szintaktikaval akarjuk ezt leirni:

a.c[0-9]d[^EFG]

Azt viszont program modositas nelkul, csak a CV tablaval mar _nem_
erhetjuk el, hogy a regular expression * -jat is kezelje, ami
akarmilyen hosszu string-re illeszkedik. Alternativak kereseset
viszont (amirol z2 is irt) pici programmodositassal lehet elerni: A
'string kezdodik' or-olast, meg a 'string vege' feltetelt kell csak
modositani, es maradhat minden ugyanigy, ha a ket vagy tobb
alternativa egyuttes hossza nem tobb 32-nel.

Fontos erdekessege meg az algoritmusnak, hogy konnyen lehet belole
olyat is kihozni (programmodositassal persze), hogy elviseljen
nehany (mondjuk egy) kulonbseget, vagy delete-et, vagy insert-et!
Errol a 'Fuzzy' keresesrol (nem azonos a fuzzy logikaval) legkozelebb
irok majd, mert felek, hogy tullepem a sor limitet.

(Apropo, moderatorok, illetve Hix :) Jozsi: nem lehetne nagyobbra
venni a sor limitet? :)

István
--  Istvan Marosi  --  http://www.sch.bme.hu/~marosi  --
--  Recosoft Ltd.  --  mailto:  --
+ - Re: Ujra: bitsorozatba bitsorozat kereses (mind) VÁLASZ  Feladó: (cikkei)

On 18 May 98 at 5:42, Antal Kovacs > wrote:

> A problema: Nem ismerem a keresendo bitsorozatot!!!
> Tehat a legtobb ismetlodo bitsorozat kell megtalalnia es
> le kell fedje az teljes (bit)intervallumot.

[ Mit ertesz ezen, hogy lefedni a teljes intervallumot?]

Lehet, hogy a Lemper-Ziv-Welch (LZW) algoritmusbol kellene
kiindulnod, bar szabadalmaztatva van, ugyhogy csak penzert
hasznalhato. Nem pont ezt csinalja (eredendoen tomoritesre talaltak
ki, a pkzip is hasznalja/hasznalta), tehat nem garantalja, hogy az
osszes ismetlodo sorozatot megtalalja, de nagyon egyszeru algoritmus,
idoben linearis a string hosszaval, es egyszeru kodolni is.
Statisztikailag elegendoen hosszu string eseten nagy valoszinuseggel
a legtobbszor elofordulo leghosszabb stringet lehet vele megtalalni.
Ha tobbszor vegigfuttatod, akkor viszont egyre pontosabban konvergal
a keresett dologhoz. Lehet, hogy ketszer futtava is mar eleg jo
eredmenyt ad, kerdes, hogy mire kell.

Leirnam, hogy hogyan mukodik, de akkor a masik cikkel egyutt mar tuti
tullepem a mai sorlimitet :(

István
--  Istvan Marosi  --  http://www.sch.bme.hu/~marosi  --
--  Recosoft Ltd.  --  mailto:  --
+ - Grafikus kepallomany pascal hatterkent (mind) VÁLASZ  Feladó: (cikkei)

Tud valaki segiteni nekem, hogy GIF, PCX, BMP vagy egyeb szabvanyos
grafikus allomanyt betoltsek pascal hatterkepkent, s arra meg tudjak
is rajzolni?
Koszi:
       Zsolt
+ - [DOS] int 21 ReadLN (mind) VÁLASZ  Feladó: (cikkei)

Ave!

  A kovi rutin egy readln lenne, csakhogy nem ertem :(
    mov dx,offset ide
    mov cx,8          <- max ennyi karakterk olvas be
    xor bx,bx         <- billentyuzetrol olvas
    mov ah,3fh
    int 21h
A hiba: ha bekeresnel tobb, mint 8 karakter irok be,
akkor a kovetkezo meghivasnal egybol kilep s visszaadja
az elozoleg beirt felesleget. Tehat ay elso hivasnal beirom:
HAJRA LOKI
ekkor a visszadott ertek: 8 byte = "HAJRA LO"
ezutan megint meghivom, nem var semmire,
hibat nem jelezve kilep, s visszadja:
4 byte = "KI"#13#10
Nem ertem!!!! Segitseg!!!!

Bye,
     Tooth 'Gabry' Gaabor
     mailto:
     post:H-4001 Debrecen P.O. Box 515, HUNGARY
--
OFFLINE CHAT with ELIZA (sponsored by Gabry :)
ELIZA: HI, I AM ELIZA TELL ME YOUR PROBLEM
YOU: .(roviden) valaszolj angolul es kuld vissza.
+ - Re: Ujra: bitsorozatba bitsorozat kereses (mind) VÁLASZ  Feladó: (cikkei)

>Tehat a legtobb ismetlodo bitsorozat kell megtalalnia es
              ********************
>le kell fedje az teljes (bit)intervallumot.


Ezt (*)  valahogy definialnod kellene, nekem nem sikerult semmi ertelmeset
kitalalni :)

Bit alapu tomoritesen torod a fejed ?

z2
+ - VISUAL BASIC 100% CPU (mind) VÁLASZ  Feladó: (cikkei)

Visual Basicben a programom sok egyébb program mellett fut. Timer által
meghatározott idonként végzek el dolgokat, de ilyenkor a progi magához
rendeli az összes lehetséges CPU-t. Mindenki másnak kuss van. Valaki
megoldotta már ezt a problémát;
+ - WinWord header ? (mind) VÁLASZ  Feladó: (cikkei)

Taliho !

WinWord documentumrol szeretnem megtudni, hogy Documentumkent
vagy Sablonkent lett-e elmentve, anelkul hogy a WinWord rendelkezesemre
allna az adott gepen.

Ehhez kerek toletek segitseget !

Ugy tudom minden Word verzionak mas a header-e. Tehat elso lepesben a
verzio szamot kell megtudni belole, aztan johet a megfelelo helyen a jelzo
bit keresese.
Ha valakinek van leirasa vagy tapasztalata, kerem ne kimeljen !

BeGa

AGYKONTROLL ALLAT AUTO AZSIA BUDAPEST CODER DOSZ FELVIDEK FILM FILOZOFIA FORUM GURU HANG HIPHOP HIRDETES HIRMONDO HIXDVD HUDOM HUNGARY JATEK KEP KONYHA KONYV KORNYESZ KUKKER KULTURA LINUX MAGELLAN MAHAL MOBIL MOKA MOZAIK NARANCS NARANCS1 NY NYELV OTTHON OTTHONKA PARA RANDI REJTVENY SCM SPORT SZABAD SZALON TANC TIPP TUDOMANY UK UTAZAS UTLEVEL VITA WEBMESTER WINDOWS