Patent ID: 11899724
Assignee: NEC CORPORATION
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 0:
1. An order preserving pattern matching apparatus comprising:
one or more processors; and
a memory storing program code executable by the one or more processors to:
for each of a plurality of matching directions in a retrieval pattern, set an ID number for each of a plurality of order preserving types of a character string for the matching direction, the retrieval pattern composed of text data arranged two-dimensionally, the plurality of matching directions including at least one diagonal direction;
for each matching direction in the retrieval pattern, generate a matching direction pattern as a list of ID numbers that include the ID number for each order preserving type of the character string for the matching direction;
for the matching direction pattern for each matching direction, generate as index information for the retrieval pattern an index specifying an order preserving pattern for the list of ID numbers for the matching direction pattern;
for an input two-dimensional pattern, generate an encoded two-dimensional pattern corresponding to the input two-dimensional pattern using the index for the matching direction pattern for each matching direction, the encoded two-dimensional pattern including each ID number of the list of ID numbers for the matching direction pattern, the input two-dimensional pattern composed of text data arranged two-dimensionally and including an array larger than that of the retrieval pattern;
for the matching direction pattern for each matching direction, determine whether an arrangement matching the list of ID numbers for the matching direction pattern exists or not within the encoded two-dimensional pattern; and
for the matching direction pattern for each matching direction for which the arrangement matching the list of ID numbers for the matching direction pattern exists, output a matching position where the arrangement exists, wherein
index information is an automaton constituted by branches that branch based on a magnitude relation of consecutive values, and
usage of the index information improves data mining by providing for order preservation during search of the input two-dimensional pattern.