# US 2003/0074183 A1 · Method and system for encoding and accessing linguistic frequency data

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2003/0074183 A1
- Document ID: US20030074183A1
- Status: Published application
- Kind: A1
- Application number: 09/977,304
- Filed: 2001-10-16
- Published: 2003-04-17
- Earliest claimed: 2001-10-16
- Assignees: Xerox Corporation
- Inventors: Andreas Eisele
- Web page: https://patentgrep.com/patent/US20030074183A1

## CPC

- G06F 40/216: using statistical methods
- G06F 40/123: Storage facilities
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Linguistic frequency data is encoded by identifying a plurality of sets of character strings in a source text, where each set comprises at least a first and a second character string. Frequency data is obtained for each set and stored at a memory position in a first memory array that is assigned to each first character string. A pointer pointing to a position in the first memory array that has been assigned to the corresponding first character string of the respective set and which has stored the frequency data of the respective set, is stored in a second memory array for each set comprising each character string that is a second character string. The encoded data is accessed by identifying regions in the memory arrays that are each assigned a search string and a pointer pointing to a position in the first memory array.

## Claims

### Claim 1

Method of encoding linguistic frequency data, the method comprising:
identifying a plurality of sets of character strings in a source text, each set comprising at least a first and a second character string,
for each set, obtaining frequency data indicative of the frequency of the respective set in the source text,
for each character string that is a first character string in at least one of the sets, assigning a memory position in a first memory array to the respective character string and storing at said memory position the frequency data of each set comprising the respective character string as first character string, and
for each character string that is a second character string in at least one of the sets, assigning a memory position in a second memory array to the respective character string and storing at said memory position, for each set comprising the respective character string as second character string, a pointer pointing to a memory position in the first memory array assigned to the corresponding first character string of the respective set and having stored the frequency data of the respective set.

### Claim 2 (depends on 1)

The method of claim 1 wherein each set of character strings further comprises a third character string, and the method further comprises:
for each character string that is a third character string in at least one of the sets, assigning a memory position in a third memory array to the respective character string and storing at said memory position, for each set comprising the respective character string as third character string, a pointer pointing to a memory position in the second memory array assigned to the corresponding second character string of the respective set and having stored a pointer pointing to the frequency data of the respective set.

### Claim 3 (depends on 1)

The method of claim 1 wherein each character string is a word of a natural language.

### Claim 4 (depends on 1)

The method of claim 1 wherein each set of character strings comprising n character strings, n being an integer number greater than one, each set being an n-gram.

### Claim 5 (depends on 4)

The method of claim 4 wherein n is equal to 3, the n-grams being trigrams.

### Claim 6 (depends on 1)

The method of claim 1 wherein said frequency data indicative of the frequency of the respective set in the source text includes the number of occurrences of the respective set in the source text.

### Claim 7 (depends on 1)

The method of claim 1 wherein said frequency data indicative of the frequency of the respective set in the source text includes weight numbers of a maximum entropy model.

### Claim 8 (depends on 1)

The method of claim 1, further comprising:
mapping each character string occurring in the source text to a numeric identifier identifying the character string, by operating a finite-state machine.

### Claim 9 (depends on 8)

The method of claim 8, further comprising:
storing the memory positions assigned to the respective first character strings in a first positional array,
storing the memory positions assigned to the respective second character strings in a second positional array, and
using the numeric identifiers to query the positional arrays for assigning the memory positions to the character strings.

### Claim 10 (depends on 1)

The method of claim 1, further comprising:
accessing a hash-table for assigning a numeric identifier to each character string occurring in the source text.

### Claim 11 (depends on 10)

The method of claim 10, further comprising:
storing the memory positions assigned to the respective first character strings in a first positional array,
storing the memory positions assigned to the respective second character strings in a second positional array, and
using the numeric identifiers to query the positional arrays for assigning the memory positions to the character strings.

### Claim 12 (depends on 1)

The method of claim 1, further comprising:
in the second memory array, sorting the pointers relating to the same second character string, with respect to the memory positions of the first memory array to which the pointers point.

### Claim 13 (depends on 1)

The method of claim 1 wherein the pointers are stored in compressed form.

### Claim 14

Method of accessing encoded linguistic frequency data for retrieving the frequency of a search key in a text, the search key comprising a first and a second search string, the encoded data being stored in a first memory array storing frequency data and a second memory array storing pointers to the first memory array, the frequency data being indicative of the frequencies of character sets in a source text, the character sets each including at least two character strings, the method comprising:
identifying a region in the first memory array that is assigned to the first search string,
identifying a region in the second memory array that is assigned to the second search string,
identifying a pointer stored in the region of the second memory array, pointing to a memory position within the region of the first memory array, and
reading the frequency data stored at said memory position.

### Claim 15 (depends on 14)

The method of claim 14 wherein the search key further comprises a third search string and the encoded data is further stored in a third memory array storing pointers to the second memory array, wherein the method further comprises:
identifying a region in the third memory array that is assigned to the third search string,
identifying a pointer stored in the region of the third memory array, pointing to a memory position within the region of the second memory array, and
tracing the pointer stored in the region of the third memory array back until the region of the first memory array is reached.

### Claim 16 (depends on 14)

The method of claim 14 wherein each character string is a word of a natural language.

### Claim 17 (depends on 14)

The method of claim 14 wherein each set of character strings comprising n character strings, n being an integer number greater than one, each set being an n-gram.

### Claim 18 (depends on 14)

The method of claim 14 wherein n is equal to 3, the n-grams being trigrams.

### Claim 19 (depends on 14)

The method of claim 14 wherein said frequency data indicative of the frequency of the respective set in the source text includes the number of occurrences of the respective set in the source text.

### Claim 20 (depends on 14)

The method of claim 14 wherein said frequency data indicative of the frequency of the respective set in the source text includes weight numbers of a maximum entropy model.

### Claim 21 (depends on 14)

The method of claim 14 wherein identifying a pointer includes performing a binary search within the second memory array.

### Claim 22 (depends on 14)

The method of claim 14 wherein identifying a pointer includes identifying a sub-interval in the region of the second memory array, the sub-interval including at least two pointers pointing to a memory position within the region of the first memory array.

### Claim 23 (depends on 14)

The method of claim 14, wherein identifying a pointer includes performing a first binary search for a set of pairs of strings where the first string in each pair matches the first search string, performing a second binary search for a set of pairs of strings where the second string in each pair matches the second search string, and calculating an intersection of both sets.

### Claim 24 (depends on 14)

The method of claim 14, further comprising:
if the character sets in the source text comprise more character strings than the search key, arranging the search strings in the search key such that the potentially missing search strings appear first.

### Claim 25

A system for encoding linguistic frequency data, comprising:
a processing unit for identifying a plurality of sets of character strings in a source text, each set comprising at least a first and a second character string, and, for each set, obtaining frequency data indicative of the frequency of the respective set in the source text, and
an encoder that, for each character string that is a first character string in at least one of the sets, assigns a memory position in a first memory array to the respective character string and stores at said memory position the frequency data of each set comprising the respective character string as first character string, and that, for each character string that is a second character string in at least one of the sets, assigns a memory position in a second memory array to the respective character string and stores at said memory position, for each set comprising the respective character string as second character string, a pointer pointing to a memory position in the first memory array assigned to the corresponding first character string of the respective set and having stored the frequency data of the respective set.

### Claim 26

A system for accessing encoded linguistic frequency data for retrieving the frequency of a search key in a text, the search key comprising a first and a second search string, the encoded data being stored in a first memory array storing frequency data and a second memory array storing pointers to the first memory array, the frequency data being indicative of the frequencies of character sets in a source text, the character sets each including at least two character strings, the system comprising:
an input device for inputting the search key, and
a search engine for identifying a region in the first memory array that is assigned to the first search string, identifying a region in the second memory array that is assigned to the second search string, identifying a pointer stored in the region of the second memory array, the pointer pointing to a memory position within the region of the first memory array, and reading the frequency data stored at said memory position.
