Order preserving pattern matching apparatus, order preserving pattern matching method, and computer-readable medium storing program

An order preserving pattern matching method comprising:

• for each of a plurality of matching directions in a retrieval pattern, setting, by a processor, 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, generating, by a processor, 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, generating, by the processor, 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, generating, by the processor, 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, determining, by the processor, 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, outputting, by the processor, 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.

A non-transitory computer-readable medium storing an order preserving pattern matching program executable by a computer to perform:

• for each of a plurality of matching directions in a retrieval pattern, setting 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, generating 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, generating 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, generating 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, determining 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, outputting 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.