FI102425B - Förfarande för bildande av minne - Google Patents

Claims (14)

1. Förfarande för att ästadkomma ett minne, i vilket minne data lagras i form av dataenheter, varvid ett eget minnesutrymme reserveras för var och en enhet, eniigt vilket förfarande 5. minnet genomförs i form av en registerkonstruktion, som bestär av en trädlik hierarki med noder pä flera olika niväer, varvid en individuell nod kan vara (i) en trie-nod, som innefattar en tabell, där ett enskilt element kan innehälla adressen tili en nod som är lägre i den trädlika hierarkin och där det enskilda elementet ocksä kan vara tomt, eller (ii) en hink, som innehäller 10 ätminstone ett element pä sädant sätt, att ett enskilt element i hinken är vald frän en grupp, som innefattar en dataenhet, en pekare tili en lagrad dataenhet, en pekare tili en annan registerkonstruktion och en annan registerkonstruktion, - i registerkonstruktionen utförs adressberäkning pä sädant sätt, att - (a) ett pä förhand bestämt antal bitar väljs i noden som är pä 15 den högsta nivän i den trädlika hierarkin frän en bitföljd som bildas av använda söknycklar, ett sökord bildas frän de valda bitama, pä basen av vilket man i ifrägavarande nod söker adressen tili följande nod och fortsätter tili nämnda nod, - (b) ett pä förhand bestämt antal bitar väljs bland de bitar 20 som ännu inte valts frän bitföljden som bildats av använda söknycklar och ett sökord bildas frän de valda bitama, med hjälp av vilket man igen söker adressen tili en ny nod pä lägre nivä frän tabellen i den nod till vilken man fortsatt, - steg (b) upprepas tills man kommer till ett tomt element eller tills adressen pä en ny nod är lika med hinkens adress, 25 kännetecknat därav, att tabellerna av trie-noderna genomförs stationärt som fymoder av en storlek av fyra element och ätminstone i en del av registerkonstruktionen er-sätts successive grupper av fymoder med kompresserade noder pä sädant sätt, att en enskild grupp, som bestär av sinsemellan successiva fymoder, dä . 30 det frän var och en fyrnod finns endast en adress tili en fyrnod pä en lägre nivä, ersätts med en kompresserad nod (CN), i vilken lagras adressen tili den fyrnod, mot vilken den understa noden i den gruppen av noder som skall ersättas pekar, uppgiften om värdet pä det sökord, med vilket man finner nämnda adress samt informationen om totala antalet bitar, av vitka man bildar 35 sökord i den gruppen av noder som skall ersättas. 21 102425

2. Förfarande enligt patentkrav 1, känneteckn at därav, att ersättning utförs j hela rekgisterkonstruktionen pä sädant sätt, att alla de nämda gruppema ersätts med kompresserade noder.

3. Förfarande enligt patentkrav 1, kännetecknat därav, att 5 ersättningen ocksä utförs för en grupp, tili vilken hör endast en fymod, varvid det totala antalet bitar som skall lagras svarar mot det antal bitar av vilka man bildar ett sökord i nämnda fymod.

4. Förfarande enligt patentkrav 1,kännetecknat därav, att flera successive kompresserade noder bildas i registerkonstruktionen pä sädant 10 sätt, att sökordsbitar som skall undersökas och vars antal svarar mot den använda ordlängden samlas i ätminstone den kompresserade noden pä den högsta nivän.

5. Förfarande enligt patentkrav 1, kännetecknat därav, att flera successiva kompresserade noder förenas tili en enda ny kompresserad 15 nod, varvid summan av antalen som erhälls frän de nodema som skall förenas lagras i den nya noden som antalet bitar.

6. Förfarande enligt patentkrav 1, kännetecknat därav, att en kedja av sädana successiva kompresserade noder där antalet bitar som skall undersökas ätminstone i de tvä översta nodema svarar mot den använda 20 ordlängden, ersätts med en enda samlande nod (CN4), som innehäller: - adressen till den nod tili vilken noden som är underst i kedjan innehäller en adress, - summan av antalet bitar som skall undersökas, vilken summa erhäl-lits frän nodema i kedjan, och 25. sökordsvärdena i nodema av kedjan i ordningsföljd.

7. Förfarande enligt patentkrav 1, kännetecknat därav, att minst tvä adresser tili en nod pä en lägre nivä upprätthälles i alla icke-komp-resserade fymoder av minnet.

8. Förfarande för att ästadkomma ett minne, i vilket minne data lagras . 30 i form av dataenheter, varvid ett eget minnesutrymme reserveras för var och en enhet, enligt vilket förfarande - minnet genomförs i form av en registerkonstruktion, som bestär av en trädlik hierarki med noder pä flera olika niväer, varvid en individuell nod kan vara (i) en inre nod, som innefattar en tabell, där ett enskilt element kan 35 innehälla adressen tili en nod som är lägre i den trädlika hierarkin och där det enskilda elementet ocksä kan vara tomt, eller (ii) ett blad, som innehäller 22 102425 ätminstone ett element, av en typ, som är vald frän en grupp, som innefattar en pekare tili en lagrad dataenhet och en pekare tili en nod i en annan regis-terkonstruktion, - i registerkonstruktionen utförs adressberäkning pä sädant sätt, att 5 - (a) ett pä förhand bestämt antal bitar väljs i noden som är pä den högsta nivän i den trädlika hierarkin frän en bitföljd som bildas av använda söknycklar, ett sökord bildas frän de valda bitama, pä basen av vilket man i ifrägavarande nod söker adressen tili följande nod och fortsätter tili nämnda nod, 10 -(b) ett pä förhand bestämt antal bitar väljs bland de bitar som ännu inte valts frän bitföljden som bildats av använda söknycklar och ett sökord bildas frän de valda bitarna, med hjälp av vilket man igen söker adressen tili en ny nod pä lägre nivä frän tabellen i den nod till vilken man fortsatt, - steg (b) upprepas tills man kommer till ett tomt element eller tills 15 adressen pä en ny nod är lika med bladets adress, kännetecknat därav, att tabellema av de inre nodema genomförs stationärt som fymoder av en storlek av fyra element och ätminstone i en del av registerkonstruktionen ersätts successive grupper av fymoder med kompresserade noder pä sädant 20 sätt, att en enskild grupp, som bestär av sinsemellan successive fymoder, dä det frän var och en fymod finns endast en adress tili en fyrnod pä en lägre nivä, ersätts med en kompresserad nod (CN), i vilken lagras adressen tili den fymod, mot vilken den understa noden i den gruppen som skall ersättas noder pekar, uppgiften om värdet pä det sökord, med vilket man finner nämnda 25 adress samt informationen om totala antalet bitar, av vilka man bildar sökord i den gruppen av noder som skall ersättas.

9. Förfarande enligt patentkrav 8, kännetecknat därav, att ersättning utförs i hela rekgisterkonstruktionen pä sädant sätt, att alla de nämda gruppema ersätts med kompresserade noder. 30

10. Förfarande enligt patentkrav 8, kännetecknat därav, att ersättningen ocksä utförs för en grupp, tili vilken hör endast en fyrnod, varvid det totala antalet bitar som skall lagras svarar mot det antal bitar av vilka man bildar ett sökord i nämnda fymod.

11. Förfarande enligt patentkrav 8, kännetecknat därav, att 35 flera successiva kompresserade noder bildas i registerkonstruktionen pä sädant sätt, att sökordsbitar som skall undersökas och vars antal svarar mot 23 102425 den använda ordlängden samlas i atminstone den kompresserade noden pä den högsta nivän.

12. Förfarande enligt patentkrav 8, kännetecknat därav, att flera successive kompresserade noder förenas tili en enda ny kompresserad 5 nod, varvid summan av antalen som erhälls frän de förenade noderna lagras i den nya noden som antalet bitar.

13. Förfarande enligt patentkrav 11, kännetecknat därav, att en kedja av sädana successive kompresserade noder där antalet bitar som skall undersökas ätminstone i de tvä översta noderna svarar mot den använda 10 ordlängden, ersätts med en enda samlande nod (CN4), som innehäller: - adressen till den nod tili vilken noden som är underst i kedjan innehäller en adress, - summan av antalet bitar som erhällits frän noderna i kedjan, och - sökordsvärdena i noderna av kedjan i ordningsföljd. 15

14. Förfarande enligt patentkrav 8, kännetecknat därav, att minst tvä adresser tili en nod pä en lägre nivä upprätthälles i alla icke-komp-resserade fymoder av minnet.