SE513248C2 - Metod för hantering av datastrukturer - Google Patents

Description

15 20 25 30 513t2lš8 uppsättning nummer. En tänkbar tillämpning är t ex nummer, som finns på en svart lista, vilka inte skall kunna nås för samtal utifrån. Detta exempel är ekvivalent med att hitta ett givet ord i ett elektroniskt lexikon. Ett exempel enligt teknikens ståndpunkt på denna implementation använder datastrukturer som är implementerade som register av länkade listor. Registren är vektorer av pekare med ett element för varje värde (t ex en siffra). När ett svartlistat telefonnummer infogas erhålls en länkad lista med register, som slutar i ett register, där elementet för det sista numret innehåller en nollpekare. Sökning genom dessa listor och att hitta en sekvens av nummer som inte hör till något av de infogade numren möjliggör för samtalet att fortsätta. Detta exempel kommer att beskrivas närmare med hänvisning till en ritning nedan.

Denna struktur tillåter detektering av icke giltiga nummer med ett minimum av information; så snart som ett icke existerande element påträffas eller sökningen försöker att fortsätta förbi en noll- pekare kan den avslutas med ett negativt resultat.

Problemet med denna s k enkelregistertypstruktur är att den är mycket utrymmeskrävande för lagring av långa sekvenser. I det allmänna fallet kommer endast de initiala registren att innehålla mer än ett aktuellt element. Därför kommer det att finnas stora mängder outnyttjat utrymme för de efterföljande symbolerna.

Ett annat dokument enligt teknikens ståndpunkt har publicerats av Sussenguth: "Use of Tree Structures for Processing Files", Comm of the ACM, Vol. 6, No. användning av trädstrukturer för att behandla filer. I första hand 5, maj 1963. Här beskriver Sussenguth beskriver Sussenguth en tillämpning vid sökning och uppdatering av stora filer med nyckelvärden av varierande längd och initiala sammanträffanden. En särskild tillämpning av detta är lagring av Detta lexikondata, t ex för stavningskontroller och översättare.

W U 20 25 30 513 243 3 dokument enligt teknikens ståndpunkt kommer också att beskrivas närmare nedan och med hänvisning till en figur.

I den internationella IBM ansökan ÉCT/EP94/02135 föreslås en utformning, där problemet med att hitta en bästa matchning för nycklar med olika längd, t ex IP-adresser i ett routersystem angrips. Lösningen för optimeringsprinciperna och sökförfarandena är emellertid andra än de som beskrivs i föreliggande ansökning.

REDOGÖRELSE FÖR UPPFINNINGEN I litteraturen inom mjukvarutekniken beskrivs trie "reTRIBve") (för lagrings/sökförfarandet som ett vanligt sätt att hantera "lexikon"-data, som skall genomsökas för att ta reda på om ett givet ord finns eller inte. Utrymmeskraven för trie uppmärksammas också och olika förfaranden för att begränsa dessa krav föreslås. Det verkar emellertid saknas förfaranden som på ett enkelt sätt sparar utrymme och samtidigt bibehåller sök- hastigheten.

Kärnan i föreliggande uppfinningen är sättet pà vilket förfaranden enligt teknikens ståndpunkt kombineras tillsammans med nya funktioner för att bilda en lösning i vilken en datastruktur med en dubbel uppsättning register används. Detta är för att spara minnesutrymme och samtidigt ha kvar en mycket hög prestanda för operationer i tillämpningar, där man måste lagra och söka genom långa registeruppsättningar, som innehåller symboler, såsom siffror eller bokstäver.

Lösningen innefattar en datastruktur och ett förfarande för att i en datastruktur lagra, radera och hitta ord eller nummer där den N U 20 25 30 513 2428 dubbla uppsättningen av registerorgan betyder att en första uppsättning är en länkad lista av register såsom visas i teknikens ståndpunkt, men där det också finns en andra lista med strängar som innehåller de fullständiga numren. Exempel kommer att ges där lösningens fördelar tydligt kommer att framgå och där telefon- nummer används. Uppfinningen skall emellertid inte ses som begränsad endast till denna tillämpning. Andra sekvenser och symboler än nummer (t ex bokstäver) kan användas. Idén kan också användas när en snabb och effektiv hantering av symboler behövs (t ex för att söka genom elektroniska lexikon) och när maximal tid/utrymmesprestanda är viktig. Behovet av hantering av sådana datastrukturer är uppenbart dà lagring/sökning av deluppsättningar av flera tusen nummer görs i olika telekommunikationscenter och ett snabbt och utrymmeseffektivt sätt att utföra detta är viktigt för systemets prestanda.

Uppfinningens särdrag som tros vara nya framställs särskilt i de bilagda patentkraven. Själva uppfinningen kommer bäst att förstås, både i uppbyggnad och sätt att utföra samt ytterligare syften och fördelar med denna med hänvisning till den bilagda beskrivningen tagen i samband med de bilagda ritningarna.

KORTFATTAD BESKRIVNING AV RITNINGARNA Utföringsformer av uppfinningen kommer nu att beskrivas i samband med ritningarna, på vilka: - fig. 1 visar en registerlayout för att lagra siffror i en datastruktur i enlighet med teknikens ståndpunkt, - fig. 2 visar en annan registerlayout för att lagra siffror i en datastruktur i enlighet med teknikens ståndpunkt, - fig. 3 visar en förenklad registerlayout för att lagra siffror i en datastruktur i enlighet med teknikens ståndpunkt, W U 20 25 30 5.13 2i48 5 - fig. 4 - 8 visar registerlayouter vid efterföljande insättningar av tal i datastrukturen enligt uppfinningen, - fig. 9 visar ett flödesschema för insättningsproceduren enligt uppfinningen, - fig. 10 - ll visar en registerlayout för att lagra ett nummer i en datastruktur i enlighet med uppfinningen, - fig. 12 visar en tillståndsmatristabell för lagring av ett nummer i en datastruktur enligt uppfinningen, - fig. 13 visar ett flödesschema för raderingsproceduren enligt uppfinningen, - fig. 14 visar ett flödesschema för hitta/sökproceduren enligt uppfinningen och - fig. 15 visar ett diagram som visar lagringskrav för enkel respektive dubbel registertyputformning.

BESKRIVNING AV FÖREDRAGNA UTFÖRINGSFORMER Pig. 1 visar ett exempel från besläktad känd teknik, där ett förfarande beskrivs för att demonstrera hur ett svartlistat telefonnummer insätts i länkade listor av register i en enda registertypstruktur för att snabbt ta reda på om en uppringande abonnent finns på svarta listan eller inte. Ett nummer antas här inmatat siffra för siffra. Sà fort ett nummer som inte hör till nàgot av de fördefinierade numren genereras, avbryts sökningen och samtalet tillåts att fortsätta. Dessa problemområden betecknas såsom nämnts "trie search" (ursprumgligen från reTRIEve) och besläktade datastrukturer implemenfieras som länkade register- listor. Registren är vektorer med Éekare med ett element för varje värde (alfabetisk symbol i det allfiänna fallet, siffrorna O-9 i detta fall). För alla giltiga sekvenser finns en länkad register- lista som slutar i ett register där elementet för den sista 10 15 20 25 30 515 243 6 giltiga symbolen innehåller en nollpekare. Sålunda visar fig. 1 321 och 3245 skulle representeras. En position som finns i ett register betecknas med ett exempel på hur sekvenserna 123, en "x"-markering och nollpekaren betecknas med en " "-symbol.

Fig. 2 visar ett annat dokument enligt teknikens ståndpunkt, nämligen Sussenguths förfarande som beskrivs ovan. I figuren ser vi hur fem telefonnummer med nio siffror skulle kunna lagras 321456789, 334567890, Varje register i strukturen enligt enligt Sussenguth. Numren är 123456789, 351567890 och 354567890.

Sussenguths förslag består av ett nyckelvärde (t ex en siffra) och två pekarvärden. Den första pekaren pekar på ett annat register på samma nivå, dvs registret som innehåller ett nyckelvärde för samma sifferposition. Den andra pekaren pekar mot "filialuppsättningen" för alla nummer med samma initiala sekvens, åtminstone fram till det aktuella djupet (antalet siffror). Sålunda betecknar de små rutorna register som endast pekar ut en filialuppsättning. För dessa efterföljande register finns det inga pekare till register som betecknar samma sifferposition (mittelementet i registret).

Sussenguths lösning påminner om enkelregistertyp trie som beskrivs ovan, men skillnaden mellan de två förfarandena är att i Sussenguths förslag är sifferpositionerna vid några särskilda nivåer länkade med pekare i stället för att betecknas som element i en vektor.

I fig. 3 ser vi hur många strängar vi skulle behöva för samma exempel som ovan om vi här använder lagring i enkelregistertyp- strukturen, som föreslås enligt teknikens ståndpunkt. De små rutorna betecknar pekarregister, där endast ett element används.

Denna struktur kräver 814 bytes med data, jämfört med 126 bytes med data enligt uppfinningen. Beräkningarna kommer att beskrivas närmare nedan. 10 15 20 25 30 5137248 Uppfinningen föreslår à andra sidan en lösning där datastrukturen i fig. l ersätts av en dubbel uppsättning register. Den första uppsättningen är en länkad lista med register som tidigare, men det finns en andra lista med strängar som innehåller hela numren.

De länkade registren används endast så länge det finns tvâ eller fler element markerade som aktuella. Slutregisterelementet kommer att peka pà motsvarande sträng.

Fig. 4 - 8 kommer att visa hur insättningsprincipen fungerar för 321456789, 334567890, 351567890 och 354567890 siffra för siffra. I detta fall kommer symbolen " " att indikera att pekafen pekar på en annan sträng och samma sekvenser som ovan, dvs l23456789, inte på ett annat register. Figurerna 4 - 8 visar register- layouterna vid efterföljande insättningar av dessa nummer.

Vektorregistret med pekare betecknas som "typ A", medan registret med strängar som innehåller nummer betecknas som "typ B". Det första registret av typ A finns initialt, även om det inte finns några nummer definierade i listan. Alla poster i detta register är initierade som nollpekare. Insättningsproceduren för nya nummer kommer nu att beskrivas stegvis. Fig. 4 - 8 kommer också att visa resultatet av den stegvisa proceduren.

Det bör observeras att även om exemplen nedan hänför sig till hantering av telefonnummer, skulle data likaväl kunna utgöra en annan sekvens av symboler: Insättning av nya nummer 10 15 20 25 30 513 2848 1. Välj ett aktuellt register, som antingen är det första registret, eller ett register som pekas pà av den aktuella pekaren som initialt pekar pà det första A-registret. Öka djupräknaren, som är initialt satt till noll, med ett. 2. Välj nästa siffra i numret som skall sättas in. Initialt är denna lika med den första siffran. Denna kommer att kallas "aktuell siffra" i det följande. 3. Finn den aktuella pekaren vid motsvarande position i registret genom att använda värdet pá den aktuella siffran som index i det aktuella registret. Om denna pekare pekar på ett annat register av typ A, gå tillbaka till steg l, i annat fall fortsätt. 4. Om den aktuella pekaren är noll, skapa ett register av typ B och lagra hela numret i detta. Uppdatera den aktuella pekaren till att peka pà det nya B-registret. Detta avslutar insättnings- proceduren. I annat fall fortsätt. 5. Kontrollera om det aktuella B-registret innehåller samma nummervärde som numret som skall sättas in. I sådana fall avslutas insättningsproceduren med ett fel "numret finns". I annat fall fortsätt. 6. Skapa och länka i ett nytt A-register vilket också medför omdefiniering av tidigare pekare. Öka djupräknaren med ett. Sätt nästa siffra i numret som skall sättas in till aktuell siffra. 7. Välj i det aktuella B-registret siffran som svarar mot djup- räknaren. Jämför denna siffra med den aktuella siffran i numret 10 15 20 25 513 248: 9 som skall sättas in. Om dessa siffror är lika gå till steg 6, i annat fall fortsätt. 8. Skapa ett nytt B-register, insätt hela det nya numret i detta och insätt en pekare till B-registret vid en indexposition i det tidigare A-registret som svarar mot den aktuella siffran. Detta avslutar insättningsproceduren.

Genom att titta på fig. 4 - 8, ser vi resultatet av insättningen av numren 123456789, 321456789, 33456789, 35167890 och 354567890 i enlighet med den stegvisa proceduren ovan. l Fig. 4 visar insättning av det första numret. Det initiala A- registret och en B-registeringàng har definierats.

Fig. 5 visar insättning av det andra numret. En ny B-register- ingång har definierats.

Fig. 6 visar insättning av det tredje numret. Ett nytt A-register har skapats och en ny B-registeringàng definieras och den tidigare pekaren till det andra insatta numret har omdefinierats.

Fig. 7 visar insättning av det fjärde numret. En ny B-register- ingång har definierats.

Fig. 8 visar insättning av det femte och sista numret i detta exempel. Ytterligare ett nytt A-register behövs här. Här ser vi också hur den tidigare pekaren (tiil det fjärde numret) har omdefinierats. 10 15 20 25 30 513 248 10 Modus operandi för insättningsproceduren i enlighet med uppfinningen kan enkelt visas i ett flödesschema som visas i fig. 9.

Ur tabellen i fig. 12 med de bilagda figurerna 10 - ll visas ytterligare ett klargörande av förfarandet. Här visar vi en beskrivning i tillstàndsmatrisform av insättning av det femte och (354567890) och 11 (efter) visas här med hänvisningsbeteckningar. sista numret i exemplet som gavs ovan. Fig. 10 (före) Denna insättningsprocedur är nu utrymmeseffektiv och bibehåller samtidigt sökhastigheten. En utvidgning av idén kan implementeras inom uppfinningens omfång för att skapa ett enda allmänt uppfinningskoncept. Genom att använda insättningsförfarandet som beskrivs ovan blir ett förfarande för radering av nummer och ett förfarande för att hitta nummer i registren en naturlig utvidgning av idén. En stegvis förklaring raderings- och hitta/sökproceduren tillsammans med fig. 11 och 12 som visar de relevanta flödes- schemana kommer att belysa förfarandena.

Radering av ett existerande nummer 1. Välj ett aktuellt register, som antingen är det första registret, eller ett register som pekas ut av den aktuella pekaren. Öka djupräknaren, som initialt är satt till noll med ett. 2. Välj nästa siffra i numret som skall raderas. Initialt är denna satt lika med den första siffran. Denna kommer att kallas "aktuell siffra" i den följande beskrivningen. 10 15 20 25 513 248 11 3. Finn en ny aktuell pekare vid motsvarande läge i registret genom att använda värdet pà den aktuella siffran som index i det aktuella registret. Lagra värdet av den aktuella pekaren i en temporär vektor vid ett indexvärde som svarar mot djupräknaren. Om denna pekare pekar pà ett annat register av typ A gå tillbaka till steg 1, i annat fall fortsätt. 4. Om den aktuella pekaren innehåller ett nollvärde avslutas raderingsproceduren med ett fel "ej hittat". 5. Annars, om den aktuella pekaren pekar pà ett register av typ B, kontrollera om numret som finns i detta B-register är samma som det som skall raderas. I så fall radera detta register, annars avsluta med ett fel "ej hittat". 6. Sätt den aktuella B-pekaren i A-registret till noll. 7. Om det finns fler än en B-pekare eller någon A-pekare i det aktuella A-registret avslutas raderingsproceduren. 8. Annars, om det endast finns en Bepekare kvar i det aktuella A- registret, raderas detta A-register, B-pekaren flyttas till det tidigare A-registret och gör detta till aktuella registret och ersätter A-pekaren till det raderade registret med B-pekaren. Gå tillbaka till steg 7.

Hitta ett nummer N Ü 20 25 30 513. 248 12 1. Välj ett aktuellt register, som antingen är det första registret, eller ett register som utpekas av den aktuella pekaren. Öka djupräknaren, som initialt är satt till noll med ett.

Initialt är denna "aktuell 2. Välj nästa siffra i numret som skall hittas. lika med den första siffran. Denna kommer att kallas siffra" i den följande beskrivningen. 3. Hitta en ny aktuell pekare vid motsvarande position i registret genom att använda värdet på den aktuella siffran som index i det aktuella registret. Om denna pekare pekar pà ett annat register av typ A, gå tillbaka till steg 1, i annat fall fortsätt. 4. Om den aktuella pekaren innehåller ett nollvärde, avslutas sökproceduren med "ej hittat". 5. Annars, om den aktuella pekaren pekar på ett register av typ B, hämta detta register som ett möjligt nummer. 6. Scanna det möjliga numret siffra för siffra och jämför med motsvarande siffror i numret som skall hittas. Om siffrorna inte matchar vid motsvarande positioner eller om numren har olika längd, avsluta med "ej hittat". Om alla siffror i båda numren som jämförs är lika, avsluta sökningen med "hittat".

Utrymmeskraven för insättningsexemplet ovan med fem nummer med nio' siffror var jämför sig med teknikens ståndpunkt som följer: fallet med den enkla registertypen i fig. 1 skulle kräva 37 register, eller 814 bytes såsom ses i fig. 3 där de mindre rutorna motsvarar pekarregister där endast ett element används, varvid det antas att varje pekare är 2 bytes, vilket gör totalt 20 bytes för pekare och 10 15 20 25 30 5130248 13 att det finns 2 extra bytes för flaggor (finns/finns inte) per register, dvs 22 bytes per register.

Sussenguthförfarandet sàsom visas i fig. 2 skulle för samma exempel medföra ett behov av 4lx5 = 205 bytes lagringsutrymme, om det antas att varje register är 2x2 bytes för pekare och 1 byte för nyckeln (siffran).

Fallet med ett register av dubbeltyp i enlighet med uppfinningen skulle kräva tre pekarvektorregister och fem strängregister (fig. 8). Med antagandet att varje strängregister är dimensionerat att innehålla 24 siffror (= 12 bytes) skulle detta ge en total på 3x22 + 5x12 = fallet med enkelregister. 126 bytes, dvs omkring 15% av utrymmet som krävs för Sussenguthförfarandet är sämre än dubbelregisterförfarandet, men bättre än enkelvektorregistret som beskrivs ovan. Sökning med Sussenguthförfarandet skulle vara långsammare än med enkelvektor eller dubbelvektorförfarandet. Orsaken till att sökningen blir långsammare är att i genomsnitt måste fem pekare följas för var och en av de initiala nivåerna för att hitta en matchning/icke matchning. Datorlogiken är också mindre effektiv vid adressering av pekare än av vektorindex.

I syfte att jämföra de två förfarandena för en större uppsättning nummer med varierande längd har en matematisk simulering gjorts.

En serie pà mer än 1000 slumpnummer med slumpmässig längd, i området 2 till 24 siffror alstradesfl Fördelningen var sàdan att huvuddelen av numren hade omkring 12 siffror. Utfallet är att för 1000 nummer skulle enkelregistermodellen kräva omkring 200 k bytes, medan dubbelregistermodellen endast skulle kräva omkring 27 k bytes eller 13%. Detta visar att signifikanta mängder minne kan 10 513 248 14 sparas, vilket är viktigt då ett stort antal programmoduler tävlar om tillgång till dataminnesutrymme i t ex en telefonväxel.

Fig. 15 visar hur de två utföringsformerna är i förhållande till varandra för ett varierande antal element. Diagrammet visar utfallet för den ovan nämnda matematiska simuleringen för en specifik nummerfördelning. Analysen har gjorts på grund av slump- tal som sorteras i fallande ordning som strängar (dvs "23" har en högre sorteringsordning än "2299999").

Ansökningens idé kan användas i andra söktillämpningar där innyckelvärdet ges ett element åt gången. Detta kan tillämpas på t ex routeranalys och hemregisterplatssökningar.

Claims (4)

1. 0 15 20 25 5 13 2 8 IS PATENmmAv l. Förfarande för att hantera sekvenser av symboler i en data- struktur innefattande länkade listor av register, kännetecknat av att symbolsekvenserna insätts symbol för symbol i en dubbel uppsättning register: - en första uppsättning länkade registerlistor (A-register), som är vektorregister med pekare med ett element för varje symbol (t ex 0-9) - en andra uppsättning strängar (B-register), som innehåller hela sekvensen av inmatade symboler, varvid i ett initialskede alla element i nämnda A-register initieras som nollpekare och varvid en påföljande insättning av en sekvens av symboler innefattar stegen att: - (I) välja ett aktuellt register, som antingen är det första registret eller ett register som utpekas av den aktuella pekaren, som initialt pekar på det första A-registret och öka en djupräknare som initialt är satt till noll med ett, - (II) välja nästa symbol i sekvensen av symboler att sättas in vilken initialt kommer att vara den "första" symbolen och senare den "aktuella" symbolen, - (III) finna den aktuella pekaren vid motsvarande position i registret genom att använda värdet för den aktuella symbolen som index i det aktuella registret och om denna pekare pekar på ett annat A-register gå tillbaka till steg (I), - (IV) om den aktuella pekaren är noll, skapa ett B~register och lagra hela sekvensen med symboler i detta och uppdatera den aktuella pekaren till att peka pà det nya B-registret, vilket avslutar insättningsproceduren, och i annat fall fortsätta, 10 15 20 25 513 248 fe - (V) symbolsekvens som symbolsekvensen som skall sättas in och om kontrollera om det aktuella B-registret innehåller samma detta är fallet avsluta insättningsproceduren, och i annat fall fortsätta, - (VI) djupräknaren med ett och sätta nästa symbol i symbolsekvensen som skall sättas in till "aktuell" symbol. skapa och länka i ett nytt A-register och öka - (VII) Välja symbolen som svarar mot djupräknaren i det aktuella B-registret och jämföra denna symbol med den aktuella symbolen i symbolsekvensen som skall insättas och om dessa symboler är lika gå till steg (VI), och i annat fall fortsätta, - (VIII) symbolsekvensen i detta och sätta in en pekare till B-registret skapa ett nytt B-register, sätta in hela den nya vid en indexposition i det föregående A~registret som svarar mot den aktuella symbolen.

2. Förfarande för att hantera sekvenser av symboler i en data- struktur innefattande länkade listor av register, kännetecknat av att symbolsekvenserna insätts symbol för symbol i en dubbel uppsättning register: - en första uppsättning länkade registerlistor (A-register), som är vektorregister med pekare med ett element för varje symbol (t ex O-9) - en andra uppsättning strängar (B-register), som innehåller hela sekvensen av inmatade symboler, varvid en radering av en symbolsekvens ur nämnda register in- nefattar stegen att: - (I) välja ett aktuellt register, som antingen är det första registret eller ett register som pekas ut av den aktuella lO 15 20 25 30 513,24? /? pekaren och öka en djupräknare, med ett. som initialt är satt till noll, - (II) välja nästa symbol i symbolsekvensen att raderas som initialt är den "första" symbolen och senare den "aktuella" symbolen. - (III) registret genom att använda värdet på den aktuella symbolen som finna en ny aktuell pekare vid motsvarande position i index i det aktuella registret, lagra värdet för den aktuella pekaren i en temporär matris med ett indexvärde som svarar mot djupräknaren och om denna pekare pekar på ett annat A-register ga tillbaka till steg (I), och i annat fall fortsatta. - (IV) kontrollera om den aktuella pekaren innehåller ett noll- värde, och om så är fallet avsluta raderingsproceduren. - (V) annars, om den aktuella pekaren pekar på ett B-register, kontrollera om symbolsekvensen som finns i detta B-register är samma som skall raderas, radera och om detta är fallet, registret, och i annat fall avsluta raderingsproceduren. - (VI) Sätta den aktuella B-pekaren i A-registret till noll. - (VII) om det finns fler än en B-pekare eller någon A-pekare i det aktuella A-registret avslutas raderingsproceduren. - (VIII) annars, om det endast finns en B-pekare kvar i det aktuella A~registret, radera A-registret, flytta B-pekaren till det tidigare A-registret, varvid denna görs till aktuellt register och ersätter A-pekaren till det raderade registret med B-pekaren och gå tillbaka till steg 7.

3. Förfarande för att hantera sekvenser av symboler i en data- struktur innefattande länkade listor av register, kännetecknat av att symbolsekvenserna insätts symbol för symbol i en dubbel uppsättning register: 10 15 20 25 30 513248 IK - en första uppsättning länkade registerlistor (A-register), som är vektorregister med pekare med ett element för varje symbol (t ex O-9) - en andra uppsättning strängar (B-register), som innehåller hela sekvensen av inmatade symboler, varvid en sökning av en viss sekvens av symboler i nämnda register innefattar stegen att: ~ (I) registret eller ett register som pekas ut av den aktuella välja ett aktuellt register, som antingen är det första pekaren och öka djupräknaren, som initialt är satt till noll, med ett. - (II) välja nästa symbol i symbolsekvensen som skall hittas, vilken initialt är den första symbolen och senare den "aktuella" symbolen. - (III) registret genom att använda värdet på den aktuella symbolen som finna en ny aktuell pekare vid motsvarande position i index i det aktuella registret och om denna pekare pekar pà ett annat A-register gà tillbaka till steg (I), och i annat fall fortsätta. - (IV) kontrollera om den aktuella pekaren innehåller ett noll- värde, och om detta är fallet avsluta sökproceduren med "ej hittad". - (V) typ B, hämta detta register som en möjlig symbolsekvens. annars om den aktuella pekaren pekar på ett register av _ (VI) det med motsvarande symboler i symbolsekvensen som skall hittas scanna det möjliga numret symbol för symbol och jämföra och om symbolerna inte matchar varandra i motsvarande positioner eller om symbolsekvenserna har olika längd avslutas sökningen med "ej hittad" och om alla symbolerna i båda symbolsekvenserna har jämförts och befunnits lika, avsluta sökningen med "hittad". 513 248 M

4. Förfarande för att hantera sekvenser av symboler i en data- struktur enligt något av kraven 1 - 3, kännetecknat av att symbolerna avser siffror och symbolsekvenserna avser telefon- Iïllmmer .