Apparatus and method for producing analogically similar word based on pseudo-distances between words

• US 6,219,633 B1
• Filed: 08/06/1999
• Issued: 04/17/2001
• Est. Priority Date: 08/06/1998
• Status: Expired due to Fees

• Current Assignee: ATR Interpreting Telephony Research Laboratories
• Original Assignee: ATR Interpreting Telephony Research Laboratories
• Inventors: Lepage, Yves
• Primary Examiner(s): Thomas, Joseph
• Application Number:
  US09/369,311
• Time in Patent Office: 620 Days
• Field of Search: 704/1, 704/9, 704/10, 704/238, 704/251, 704/252, 704/255, 704/256, 704/257, 704/270, 707/531, 707/532, 707/533, 707/534, 707/5, 707/6, 707/104
• US Class Current: 704/9
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms

Abstract

In an analogically similar word production apparatus, based on three inputted unit strings, an analogically similar word which is a word analogically similar to inputted unit strings is produced at high speed without using attributes and without any finite state automaton. A pseudo-distance matrix memory stores therein only matrix elements sufficient for computation of limited pseudo distances between two letter strings, out of the elements of two pseudo-distance matrices, and more specifically, matrix elements including diagonal elements are computed by a preprocessing section and then stored in the pseudo-distance matrix memory. An analogically similar word production section, based on the three inputted unit strings, computes a status parameter (com) by looking up to the elements of the two pseudo-distance matrices stored in a pseudo-distance matrix memory, stores the status parameter into an internal parameter memory, computes minimum paths of pseudo distances represented by the two pseudo-distance matrices while updating the status parameter (com), produces an analogically similar word according to the two minimum pseudo-distance paths, and outputs the produced analogically similar word.

Claims

1. An analogically similar word production apparatus (100) for, based on first, second and third three inputted unit strings which are inputted in a predetermined order, producing an analogically similar word having properties analogically similar in a predetermined analogically similar relation to the first to third unit strings, comprising:

matrix storage means (10) for storing a plurality of elements of a first limited pseudo-distance matrix, and a plurality of elements of a second limited pseudo-distance matrix,

a number of units to be deleted or replaced toward another unit string from one unit string being expressed by a pseudo-distance,

said plurality of elements of said first limited pseudo-distance matrix being computed at locations of a part of elements of a first pseudo-distance matrix presenting pseudo-distances between partial strings of the first inputted unit string from its beginning to its end and partial strings of the second inputted unit string from its beginning to its end, said plurality of elements of said first limited pseudo-distance matrix including a diagonal band composed of diagonal elements having a predetermined width in said first pseudo-distance matrix, and including an extra band composed of elements having a predetermined further width in said first pseudo-distance matrix which are positioned outside of said diagonal band, so as to include information sufficient for computation of limited pseudo distances between the first inputted unit string and the second inputted unit string,

said plurality of elements of said second limited pseudo-distance matrix being computed at locations of a part of elements of a second pseudo-distance matrix presenting pseudo-distances between partial strings of the first inputted unit string from its beginning to its end and partial strings of the third inputted unit string from its beginning to its end, said plurality of elements of said second limited pseudo-distance matrix including a diagonal band composed of diagonal elements having a predetermined width in said second pseudo-distance matrix, and including an extra band composed of elements having a predetermined further width in said second pseudo-distance matrix which are positioned outside of said diagonal band, so as to include information sufficient for computation of limited pseudo distances between the first inputted unit string and the third inputted unit string;

preprocessing means (2, S2) for analyzing the three inputted unit strings, computing the elements of the limited first and second pseudo-distance matrices, and storing computed elements into said matrix storage means (10);

parameter storage means (51) for storing therein a status parameter (com) which is a parameter for judging whether or not four unit strings including the first, second and third inputted unit strings, and produced fourth inputted unit string are in said analogically similar relation, and which represents a number of units common to the four unit strings upon producing the fourth unit string; and

analogically similar word production means (5, S3) for, based on respective lengths of said inputted three unit strings and respective elements of said limited first and second pseudo-distance matrices which are stored in said matrix storage means (10), computing an initial value of said status parameter (com) and storing the initial value in said parameter storage means (51), thereafter, based on the status parameter (com) stored in said parameter storage means (51) and respective elements of said limited first and second pseudo-distance matrices stored in said matrix storage means (10), deciding (S63-S68) a shortest path from a last element to a first element in said first limited pseudo-distance and a shortest path from a last element to a first element in said second limited pseudo-distance while updating (S74) the status parameter (com) stored in said parameter storage means (51), by moving said paths from an element to another element in a moving direction which is either one of a diagonal direction, a horizontal direction and a vertical direction in said limited first and second pseudo-distance matrices, and then, producing and outputting the analogically similar word according to decided shortest paths of said limited first and second pseudo-distance matrices.

2. The apparatus as claimed in claim 1,

wherein the unit string is a letter string,

wherein the unit which constitutes the unit string is a letter.

3. The apparatus as claimed in claim 1,

wherein the unit string is a word string,

wherein the unit which constitutes the unit string is a word.

4. An analogically similar word production method (100) for, based on first, second and third three inputted unit strings which are inputted in a predetermined order, producing an analogically similar word having properties analogically similar in a predetermined analogically similar relation to the first to third unit strings, including steps of:

analyzing (2, S2) the inputted three unit strings, computing a plurality of elements of a first limited pseudo-distance matrix, and a plurality of elements of a second limited pseudo-distance matrix, and storing computed elements into in matrix storage means (10),

a number of units to be deleted or replaced toward another unit string from one unit string being expressed by a pseudo-distance,

said plurality of elements of said first limited pseudo-distance matrix being computed at locations of a part of elements of a first pseudo-distance matrix presenting pseudo-distances between partial strings of the first inputted unit string from its beginning to its end and partial strings of the second inputted unit string from its beginning to its end, said plurality of elements of said first limited pseudo-distance matrix including a diagonal band composed of diagonal elements having a predetermined width in said first pseudo-distance matrix, and including an extra band composed of elements having a predetermined further width in said first pseudo-distance matrix which are positioned outside of said diagonal band, so as to include information sufficient for computation of limited pseudo distances between the first inputted unit string and the second inputted unit string,

said plurality of elements of said second limited pseudo-distance matrix being computed at locations of a part of elements of a second pseudo-distance matrix presenting pseudo-distances between partial strings of the first inputted unit string from its beginning to its end and partial strings of the third inputted unit string from its beginning to its end, said plurality of elements of said second limited pseudo-distance matrix including a diagonal band composed of diagonal elements having a predetermined width in said second pseudo-distance matrix, and including an extra band composed of elements having a predetermined further width in said second pseudo-distance matrix which are positioned outside of said diagonal band, so as to include information sufficient for computation of limited pseudo distances between the first inputted unit string and the third inputted unit string;

based on respective lengths of said inputted three unit strings and respective elements of said limited first and second pseudo-distance matrices which are stored in said matrix storage means (10), computing an initial value of a status parameter (com) which is a parameter for judging whether or not four unit strings including the first, second and third inputted unit strings, and produced fourth inputted unit string are in said analogically similar relation, and which represents a number of units common to the four unit strings upon producing the fourth unit string, and then, storing the initial value in a parameter storage means (51);

based on the status parameter (com) stored in said parameter storage means (51) and respective elements of said limited first and second pseudo-distance matrices stored in said matrix storage means (10), deciding (S63-S68) a shortest path from a last element to a first element in said first limited pseudo-distance and a shortest path from a last element to a first element in said second limited pseudo-distance while updating (S74) the status parameter (com) stored in said parameter storage means (51), by moving said paths from an element to another element in a moving direction which is either one of a diagonal direction, a horizontal direction and a vertical direction in said limited first and second pseudo-distance matrix; and

producing and outputting (5, S3) the analogically similar word according to decided shortest paths of said limited first and second pseudo-distance matrices.

5. The method as claimed in claim 4,

wherein the unit string is a letter string,

wherein the unit which constitutes the unit string is a letter.

6. The method as claimed in claim 4,

wherein the unit string is a word string,

wherein the unit which constitutes the unit string is a word.