×

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
First Claim
Patent Images

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.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×