Method for storing and retreiving files by generating an array having plurality of sub-arrays each of which include a digit of file identification numbers

• US 5,761,529 A
• Filed: 12/20/1996
• Issued: 06/02/1998
• Est. Priority Date: 10/18/1994
• Status: Expired due to Fees

• Current Assignee: Lanier Healthcare LLC (3M Company)
• Original Assignee: Lanier Worldwide Incorporated (Ricoh Company Limited)
• Inventors: Raji, Alexander David, Henion, Scott Gregory, Allen, James Glen
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Kim, Ki S.
• Application Number:
  US08/771,257
• Time in Patent Office: 529 Days
• Field of Search: 395/601, 395/824, 364/225.4, 364/283.1, 707/3, 707/2, 707/100
• US Class Current: 710/4
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: H04M 11/10 with dictation recording and playback systems
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A modular digital dictation system that can be easily modified to service a variable number of dictation stations and transcription stations. The modular digital dictation station comprises a central station for receiving digitized dictation signals from a network of dictation stations, storing the voice portion of the digitized dictation signals as digitized dictation segments, and routing the digitized dictation segments to a network of transcription stations. The central station includes a plurality of line interface and signal processing cards. The number of line interface and signal processing cards connected to the central station determines how many dictation stations and transcription stations the modular digital dictation station can service. The line interface cards may be removed from or connected to the central station during operations. A fast search program is provided to quickly find files containing desired digitized dictation segments stored in the central station. The fast search program uses arrays of identification numbers to quickly retrieve the files. The first array stores the address of the files in memory in the order in which the files are created. The second array stores identification numbers corresponding to each file in the order in which the files are created. The structure of the second array facilitates quickly finding an identification number. The position of the identification in the second array corresponds to a location in the first array containing the address in the file in memory. The position of the identification number in the second array is therefore used to calculate the location of the file in memory.

Claims

1. In a computer storing a plurality of files in a memory device, each said file being assigned a unique identification number, a method of storing and quickly retrieving a selected file via said identification number assigned to said selected file, comprising the steps of:

generating a host array and storing the address of each said file in said memory device in said host array, wherein the addresses of said files are sequentially stored in said host array in the order in which the files are created;

generating a second array contemporaneously with the generation of said host array, wherein said identification numbers for said files are sequentially stored in said second array in the order in which the files are created, and wherein said second array is sub-divided into a plurality of sub-arrays, each said sub-array including a digit from each said identification number;

finding each said digit of said identification number assigned to said selected file in said second array; and

calculating a pointer to the location in said host array to the address of said selected file in said memory device based upon the position of said digits of said identification number assigned to said selected file in said second array.

2. The method of claim 1 wherein each said sub-array has a first dimension equal to the total possible number of values that the digits from the identification numbers stored in that sub-array may assume, and having a second dimension equal to the width of a bit mask generated by said computer.

3. The method of claim 2 wherein said step of finding an identification number assigned to the selected file is completed by:

generating a mask; and

successively ANDing said mask with the digits in each said sub-array that correspond to the digits of said identification numbers assigned to the selected file.

4. The method of claim 2, wherein a plurality of identification numbers can be found in said second array by:

defining values for some, but not all, digits in an identification number;

generating a mask;

successively ANDing said mask only with the digits in the sub-arrays that correspond to the defined digits in said identification number; and

calculating the locations in said host array of the addresses of all the files that are identified by said successive ANDing.

5. In a computer storing a plurality of files in a memory device, each said file being assigned a unique identification number, a fast search computer program product for retrieving said files, said fast search computer program product stored in computer-readable memory and executed by said computer comprising:

an array, said array being divided into a number of sub-arrays, with the number of sub-arrays equaling the number of digits in said identification numbers;

a host array;

a controller operating said fast search computer program product to control;

loading the address in said memory device of each file into said host array as each file is created;

loading each digit of each identification number for each file into a sub-array as each file is created, whereby one sub-array contains all the digits in a given position for each said identification number, and wherein each sub-array has a first dimension equal to the possible values of the digit stored in said sub-array and a second dimension equal to a predetermined maximum number of jobs stored in said sub-array;

selecting an identification number for a selected file to be retrieved;

generating a mask of width equal to said predetermined maximum number of jobs stored in said sub-array;

finding said selected file in said sub-arrays by ANDing said mask with a portion of each said sub-array, said portion of said sub-arrays identified by the value in said first dimension of said sub-arrays that corresponds to the value of said digits in said identifier number for said selected file;

calculating the location in said host array of the address corresponding to said selected file using the position in said sub-arrays of said digits in said identifier number for said selected file; and

retrieving said selected file from said memory device using said address from said host array.

6. The fast search computer program product of claim 5, wherein said step of loading the address in said memory device of each file into said host array and said step of loading each digit of each identification number for each file into said host array occur contemporaneously.

7. The fast search computer program product of claim 5, wherein said plurality of files exceeds said predetermined maximum number of jobs, and wherein said fast search computer program product further comprises:

a second array, said second array being divided into a number of second subarrays, with the number of second sub-arrays equaling the number of digits in said identification numbers to store file identification numbers in excess of said predetermined maximum number of jobs; and

a second host array to store addresses in excess of said predetermined maximum number of jobs.

8. The fast search computer program product of claim 5, wherein said step of selecting an identification number comprises selecting an identification number with a number of defined digits, said number of defined digits being less than the number of digits in said identification number, and wherein said step of finding said selected file comprises ANDing said mask with a portion of each said sub-array which corresponds to a defined digit.

9. In a computer storing a plurality of files in a memory device, each file having a file identification number comprising a plurality of digits, a method for storing a file in said memory device, using a host array and a pointer array, said pointer array comprising a plurality of pointer sub-arrays, comprising the steps of:

assigning a file identification number to said file;

selecting an address for storing said file;

creating an entry for said host array for said file, said host array entry comprising a pointer pointing to said address;

storing said file identification number in said pointer array so that each said digit of said file identification number is stored in a different pointer sub-array; and

storing said file at said address.

10. The method of claim 9, wherein said host array comprises a plurality of sequentially stored host array entries and said pointer array comprises a plurality of sequentially stored file identification numbers, and wherein said step of storing said file identification in said pointer array occurs contemporaneously with said step of creating an entry for said host array.

11. The method of claim 9, wherein said digits of said file identification number have a plurality of possible digit values, and wherein each pointer sub-array has a first dimension and a second dimension, said first dimension equal to said number of possible digit values, and said second dimension equal to a predetermined maximum number of file identification numbers stored in said pointer array.

12. The method of claim 11, wherein, in the event that said pointer array contains said predetermined maximum number of file identification numbers, creating a second pointer array to store an additional file identification number and creating a second host array to store an additional address pointer.

13. The method of claim 9, further comprising the steps of:

receiving a request to retrieve a selected file identified by a selected file identification number;

using said selected file identification number to identify a selected host array entry;

using said selected host array entry to identify a selected address for said selected file; and

retrieving said selected file from said selected address.

14. The method of claim 13, wherein each digit of said selected file identification number has a digit value and a digit position, and wherein said step of using said selected file identification number to identify a selected host array entry comprises:

creating a first mask for a first digit of said selected file identification number;

applying said first mask to a first portion of a first pointer sub-array to create a second mask for a second digit of said selected file identification number, said first pointer sub-array corresponding to said digit position of said first digit and said first portion of said first pointer sub-array corresponding to said digit value of said first digit;

applying said second mask to a second portion of a second pointer sub-array to create a third mask for a third digit of said selected file identification number, said second pointer sub-array corresponding to said digit position of said second digit and said second portion of said second pointer sub-array corresponding to said digit value of said second digit; and

if said selected file identification number comprises three digits, then applying said third mask to a third portion of a third pointer sub-array to identify a position within said host array corresponding to said selected host array entry, said third pointer sub-array corresponding to said digit position of said third digit and said third portion of said third pointer sub-array corresponding to said digit value of said third digit.

15. The method of claim 13, wherein said selected file identification number comprises a plurality of defined digits, said plurality of defined digits being less than all of the digits of said selected file identification number, each said defined digit having a position and a value, and wherein said step of using said selected file identification number to identify a selected host array entry comprises:

A. creating a mask for a defined digit of said selected file identification number;

B. applying said mask to a selected portion of a selected pointer sub-array to create a masked output, said selected pointer sub-array corresponding to said position of said defined digit and said selected portion of said pointer sub-array corresponding to said value of said defined digit; and

repeating said steps A and B for each defined digit until said masked output identifies a plurality of host array entries.

16. A computer-readable medium having computer executable instructions for storing and retrieving a file in a memory device using a host array and a pointer array, said pointer array comprising a plurality of pointer sub-arrays, comprising the steps of:

A. receiving a file identification number for said file, said file identification number comprising a plurality of digits;

B. selecting an address for storing said file;

C. creating an entry for said host array for said file, said host array entry comprising a pointer pointing to said address;

D. storing said file identification number in said pointer array so that each digit of said file identification number is stored in a different pointer sub-array;

E. storing said file at said address;

F. receiving a request to retrieve said file;

said request including said file identification number;

G. using said file identification number to identify said host array entry;

H. using said host array entry to identify said address; and

I. retrieving said file from said address.

17. The computer-readable medium of claim 16, wherein said digits of said file identification number have a plurality of possible digit values, and wherein each pointer sub-array has a first dimension and a second dimension, said first dimension equal to said number of possible digit values, and said second dimension equal to a predetermined maximum number of file identification numbers stored in said pointer array.

18. The computer-readable medium of claim 16, wherein said host array comprises a plurality of sequentially stored host array entries and said pointer array comprises a plurality of sequentially stored file identification numbers, and wherein said step C occurs contemporaneously with said step D.

19. The computer-readable medium of claim 16, wherein each digit of said file identification number has a digit value and a digit position, and wherein said step of using said file identification number to identify said host array entry comprises:

successively filtering said pointer sub-arrays by;

A. creating a mask for a digit of said file identification number;

B . applying said mask for said digit to a selected portion of a selected pointer sub-array to create a masked output, said selected pointer sub-array corresponding to said digit position of said digit and said selected portion of said selected pointer sub-array corresponding to said digit value of said digit;

C. repeating said steps A and B for each pointer sub-array; and

D. using said masked outputs to identify said host array entry.