Programmers - Quick search in a text file.

 ---OPEN TECHNOLOGIES---    
                                
                    
------------------------------------------
   I got a computer in mid-1992
year. From the beginning I, like everyone else, probably
deals exclusively with toys. Well, you have to
Soviet hunger for advanced technologies
delete.  So - having played enough of
all kinds of games (I still love logic games)
toys) began to look a little
go inside programs. Basicov, co-
sure.  How interesting it was to change colors, and
then the loaders.  Slowly but surely
knowledge of assembler came. The language is so
called high level, which is called
BASIC, I still don’t really know. Or rather,
I know, but I need to learn how to use it fully
I didn't have to. I immediately climbed into the wilds, about what
I never regretted it.  Already started to appear
your programs.  Even then, we began to coordinate
it is a tradition to write a system and adhere to
ok software. I deliberately share these
categories, because  many lamers mistake them
mix into a single whole.                    
                                
   Well, okay, let's go. One day... How
sounds corny.  But one day I encountered
small problem: you need to quickly and effectively
tivefind something symbolic in something
symbolic. In short, the program was written
frame "File file". So that's where it needs to be
was to find the file name using the pattern.  EU-
Naturally, it made the search primitive
way: by going through and comparing all the letters
in order.  For that program this is a "brake"
"no" action did not play a special role, but
it became interesting to come up with a smarter solution
solving this problem. Didn't have time. I'll turn it up
there was one very clever book at hand with
intriguing name "Modern computer
yuter". I am my "Sintez" in exactly this way
Tal, so I started flipping through the tricky ones
articles. And then I found the right article on the Internet.
pressing topic. But only assembly language
there was no example for the Z-80;-) I had to
write it yourself...                        
                                
   Isn't my introduction too boring?
libelous? I know, I’m silent, I repent.         
                                
   So, let's go. I won’t talk too much anymore
to harp on the topic of what and how it was - re-
let's get down to business, and therefore the tedious part of
I also skip books. We need sectors to dis-
don't save money.First, let's look at an example of a "normal"
lamer search method, which even people are guilty of
programming aces. Sometimes. Word Search
in the text is carried out by sequential
telial comparisons of letters. The word and text are
are arrays of letters. An example of such a tech-
hundred, in which we are looking for the word PICK:           
                                
P I C K                                   
P I C K                                   
  P I C K                                 
    P I C K                               
      P I C K                             
        P I C K                           
          P I C K                         
          P I C K                         
          P I C K                         
            P I C K                       
              PI C K                     
              P I C K                     
                P I C K                   
                  P I C K                 
                    P I C K               
                    P I C K               
                    P I C K               
                    P I C K               
                                
   You guessed it - red
search matches are highlighted, and blue
mismatches.  Here you can clearly see the tiredness
effectiveness of this process for searching. B
in the example, the conditional text contains 20 letters, and
word 4 letters. The word is considered found
when all the letters match. Let's start looking
matches from the beginning of the text. First letter
words are compared with the first letter of the text.
Since they matched (red color),
the second letters are compared.  This time
the letters did not match (blue color); trace-
So, the word is shifted one position
to the right and the check is performed again and with
startedwords.  And so on until everything
four letters will not match. Darkness...        
                                
   There is no assembly example of such a search
there is no point in bringing it up, because it's not real
is the purpose of the article - ONLY ADVANCED AND
PERFECT TECHNOLOGIES IN LIFE! If anyone
wishes, can find such an example in the suppression
the vast majority of application software, ra-
nerd with databases.                
                                
   Who would have thought that 30 years later
after research began in
field of cybernetics, one can significantly and
almost radically improve the method of re-
solving such a fundamental problem as
is a text search. However, in
1976 R. Boyer and J. Moore, who worked in
while at the University of Texas at Austin
found a faster way. Their idea allowed
increases search speed at least
twice during each program cycle.
Comparison of a word with a part of the text begins
from the end of the word (placed at the beginning of the current
hundred) and continues to its beginning. If
The character being checked in the word does not match
the corresponding text letter, then the word
moves to the right relative to this same
position, which we will conditionally call the support position,
until some letter again
does not coincide with the text character in this position
tions.  If this does not happen, then the word
is shifted so that its first
the letter is one space away from the reference position
interval. Cool? Of course!                  
                                
   The question immediately arises, how do they find
the next matching letter - after all, if
To do this, you need to compare letters one by one.
No, then there is no gain. There is
Another way is to create a table of distances
from the end of the word to the last occurrence
every letter in this word. Of course you need
spend some time calculating the
what table, but it needs to be done
only once;  if the text is enough
long, it's worth it. From personal experience
I'm already convinced of this.                      
                                
   It is possible that Boyer and Moore's algorithm
works faster, but as much as possible
be sure of its correctness?  B
in particular, how to ensure that when shifting
several positions to the right without passing
no comparisons were missed
falling group of letters? Content volume
the clarification is that for complete
coincidence requires the identity of all
pairs of letters, meanwhile, as groups that
are skipped, differ in at least one
position, namely in the supporting position.      
                                
   One more important thing cannot be ignored -
new nuance - in this text the words may
not to be... Then you should"to agree"
what you need to know is word size and size
text to determine along the way the
probability of coincidence.  If in progress
shift it turns out that the word has become larger,
than the remainder of the unchecked text, then de-
there is nothing more to be said there - there is no such word!
                                
   Now we should consider the second way -
on the diagram, which will immediately allow you to evaluate
the thread of his dignity. So,               
                                
PETER PIPER PICKED A PECK       
RESK                            
  RESK                          
      RESK                      
        RESK                    
            RESK                
            RECK                
            RECK                
                RESK            
                    RESK        
                     RESKRECK       
                     RECK       
                     РECK       
                                
   Calculation of the offset in the table according to which
it is necessary to omit in case of discrepancies,
happens as follows:             
             P E S K                      
             | | |__ 1                    
             | |____ 2                    
             |______ 3                    
                                
   The table itself is derived from accounting
the size of the word we are looking for in the text, i.e.
four characters:                           
                                
        A......4                         
        B......4                         
        С_______1                         
        D......4                         
        E_______2                         
        F......4                         
        G......4                         
        N.......4                         
        I......4                         
        J.......4                         
        K_______4                         
        L.......4                         
        M......4                         
        N.......4                         
        Oh......4                         
        P_______3                         
        Q......4 and so on.          
                                
   Now compare both methods by calculating
number of operations with text. Impressive
isn't it? The effectiveness of the second unconditional
fatal. All that's left is to fill the volume
project code in assembler. In BASIC too,
Probably possible, but why??? So, the contract
We assume that we need to know the size of the entered
th word (hereinafter referred to as “sample”). Usually this is de-
barks after input. If not - distort it -
myself. Now that we know the size, not me-
It would be nice to know the size of the text. If there is no
which parameter, then it will be necessary when running,
let's say on an array with variable values
its components, to produceor semi-
Check its size so you know when to
stop searching due to lack of match
ny. Oh, I screwed it up... That's it, assembler:      
                                
 EXAMPLE OF WORKING WITH SEARCH BY NAME     
           OR INCOMPLETE DATA            
------------------------------------------
                                
        ORG #6000                        
        LD HL,1 ;initial number  
        LD (NOMLI),HL ;search strings    
        LD HL,4 ;attachment size  
        LD (N_END),HL ;in GM.            
        CALL INTABL                       
        CALL 3435                         
        LD A,2                          
        CALL 5633                         
SENAME LDHL,(NOMLI) ;номер строки ГМ  
        PUSH HL                           
        CALL SUMMA      ;ее адрес         
        CALL POISK      ;поиск            
        CALL Z,EXECUT   ;найдено совпад.  
        POP  HL                           
        INC  HL         ;дальше идем      
        LD   (NOMLI),HL                   
        LD   HL,(N_END) ;проверка конца   
        DEC  HL         ;глоб.массива     
        LD   (N_END),HL ;по кол-ву но-    
        LD   A,Н        ;меров в нем      
        OR   L                            
        JR   NZ,SENAME                    
        RET             ;"NOT FOUND"      
;                                         
EXECUT LD DE,(TEXT) ;from           
        LD BC,8 ;length            
        CALL 8252 ;print           
        LD A,13                         
        RST 16                           
        RET                               
                                
 INITIALIZING A TABLE FOR SEARCH     
 Called once before searching.    
;-------------------------------------   
INTABL LD HL,ZAG ;where is the sample      
        LD DE,OBRAZ                     
        LD BC,8                         
                                
        LDIR ;....THISFOR EXAMPLE....  
;       CALL IN_NAM ;sample input     
;       EXX                               
;       LD HL,ZAG                       
;       LD DE,OBRAZ                     
;       CALL NAME ;character check
;       EXX ;and transfer to OBRAZ...   
                                
        LD B,5;......EXAMPLE......... 
;B=HOW MANY LETTERS ARE UNDERTYPED AT INPUT     
        LD A,B ;number of letters image
                        ;MUST KNOW!!!    
        DEC A                            
        JR Z,MMM1 ;1                
        LD A,8                          
        SUB B                            
        JR NZ,MMM2                      
        EI ;NO INPUT!!!     
        RET MMM1 LD A,(ZAG+7) ;end of sample    
        CP #20 ;fill byte  
        LD A,7                          
        JR Z,MMM2 ;<>8              
        INC A ;8                
MMM2 LD (NSIZE),A ;sample size   
        LD IX,OBRAZ ;sample          
 LD HL,MASIV ;shift table   
        LD DE,MASIV+1 ;for transmission  
        LD BC, 95 ;inconsistencies   
        LD (HL),A ;transmission step 
        LDIR                              
        LD HL,OBRAZ ;sample          
        LD C,A ;its lengthDEC C ;minus one on    
        ADD HL,BC ;last char.  
        LD (ENDOBR),HL;end of sample    
        LD C,B ;C=0              
        LD B,A ;B=sample length  
        DJNZ MMMЗ ;>1               
        JR MMMCH ;<1               
MMMЗ LD A,(HL) ;match check
        DEC HL ;
        SR (HL) ;characters         
        JR NZ,MMMS                      
        DJNZ MMMЗ                         
        LD HL,MASIV ;jump array 
        LD DE,MASIV+1 ;fill in 1 for  
        LD BC,95 ;step per unit   
 LD (HL),1                       
        LDIR                              
        JR MMMCH                         
MMMS LD A,(IX+0) ;symbol from sample
        SUB #20 ;adjusted to 
        LD E,A ;0 for step definition   
        LD D,С;С=0 ;if there is a mismatch 
        LD HL,MASIV ;see note!        
        ADD HL,DE                        
        LD (HL),B ;skip step for 
        INC IX ;each letter     
        DJNZ MMMS ;by image length  
MMMMCH RET ;end of operation   
                ;or JP into the search loop...--------- NOTE -------------    
;MMMS makes a correction to the array if it does not match
;responsibility of the sample and data in the global
;array for determining the step size when 
;leaving the mismatched fragment for    
;each letter from the sample.                 
;---------------------------------------  
                                
    OBTAINING A NEW ADDRESS FOR SEARCH    
;---------------------------------------  
;in:HL,0 - line number in global. array   
                                
SUMMA LD E,L                          
        LD D,H                          
        LD B,7 ;record size    
SUMM1 ADD HL,DE                        
        DJNZ SUMM1                        
        LD BC,GMASS-8 ;GM start addressADD HL, VS                        
        LD (TEXT),HL ;search address 
        RET                               
                                
 SEARCH IN A GLOBAL ARRAY BY PATTERN   
;--------------------------------------- 
POISK LD A,(NSIZE) ;sample size   
 DEC A ;become last 
PO1 LD (NSIZE+1),A;lower letter        
 LD HL,(TEXT) ;address in global mass
 LD BC, (NSIZE)                   
 LD E,A                          
        LD D,#00                        
        LD B,D                          
        ADD HL,DE ; stand at length   
        EX DE,HL ;sample in general mass
        LD HL,(ENDOBR);end of sample    
PO2 LD A,(DE) ;byte in main mass.  
        CPD ; checked against the image
        JR NZ,PO3 ;did not match        
        DEC DE ;new main byte
        RET RO ;end check   
        JR PO2                          
PO3 SUB 32 ;correction for pe-
        LD E,A ;traversing the array
        LD D,B ;leaving fragments.
        LD HL,MASIV                     
        ADD HL,DE                        
        LD A,(NSIZE+1);where did I start     
        ADD A,(HL) ;how much translation  
        SR 8 ;record size in  
                        ;global.array   
        JR C,PO1 ;continue search 
 OR A ;flag Z=0 no
        RET ;drops ???????  
                                
       SYSTEM SEARCH VARIABLES        
;---------------------------------------  
TEXT DEFS 2 ;address in GM       
NOMLI DEFS 2 ;GM line number  
N_END DEFS 2 ;number of GM lines  
ENDOBR DEFS 2 ;end of sample    
NSIZE DEFS 2 ;sample length    
OBRAZ DEFS 8 ;correct image.
ZAG DEFM "ISH";entered sample
MASIV DEFS 96 ; table for re-
                        ;jumping at   
                        ;inconsistency.  
GMASS DEFM "SASHA" ;global array
        DEFM "GRYSHA" ; for example 8    
        DEFM "MISHA" ;character size  
        DEFM "KLAVISHA"                   
        DEFS 10                        
                                
   It wasn't a very good example, but
workable. If you compile it,
then you get a working version of the search by input-
the same sample.  Taken from my program
"File file". On the other hand, I
don't care if anyone understands...
sampler example. The main thing is to get the essence
quick search ideas, understand technology
preparing this delicious dish. If
Some people found my text difficult,
what if someone misunderstood something -read
original in the book "Modern Computer"
publishers "Mir" for 1986 year. Old
book, but very useful.  On this
let me take my leave - I'm tired and want
sleep... Bye.                            
                                
July 1998 (C) MAX