Matching pattern combinations via fast array comparison

• US 9,998,140 B2
• Filed: 04/22/2013
• Issued: 06/12/2018
• Est. Priority Date: 04/22/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lehman, Tobin J., Lichtsinn, Mario H., Strong, Jr., Hovey R.
• Primary Examiner(s): Ngo, Chuong D
• Application Number:
  US13/867,596
• Publication Number:
  US 20140317161A1
• Time in Patent Office: 1,877 Days
• CPC Class Codes: H03H 7/30 Time-delay networks analogue shift registers G11C27/04
• CPC Class Codes: H03M 7/14 Conversion to or from non-weighted codes

Abstract

Methods and arrangements for providing a compressed representation of a number sequence. An input number sequence is received, as is a stored number sequence. The input number sequence is compared to the stored number sequence. The comparing includes determining a set of coefficients corresponding to the input number sequence, via solving at least one algebraic equation, the at least one algebraic equation comprising at least one of: an arithmetic equation, and an exponential equation. The comparing further includes applying at least one test to determine whether the set of coefficients identifies at least a portion of the stored number sequence as matching the entire input number sequence.

Claims

1. A method of providing a compressed representation of a number sequence, said method comprising:

utilizing a processor to execute computer code configured to perform the steps of;

receiving an input number sequence representing an atomic service having a predetermined duration, wherein the input number sequence comprises a plurality of elements, wherein a number of the plurality of elements corresponds to a number of units of time within the predetermined duration represented as an array;

determining a set of coefficients describing the input number sequence, via solving at least one algebraic equation, the at least one algebraic equation comprising at least one of;

an arithmetic equation, and an exponential equation;

accessing a library of stored number sequences, the number sequences comprising at least one of;

arithmetic number sequences, and exponential number sequences;

determining a representation of the stored number sequences;

ascertaining a match of the set of coefficients with respect to the representation of the stored number sequences, wherein the ascertaining a match is performed by partitioning the representation of the stored number sequences into equivalence sets by performing a linear transformation test, a constant multiple test, a constant multiple of a product test, and a constant multiple of sum test on the input number sequence to reduce a number of stored number sequences to be considered when ascertaining a match and increasing a speed for ascertaining a match;

the ascertaining a match comprising;

determining, by performing the linear transformation test, whether the input number sequence is at least one of;

a linear transformation of at least one of the representation of the stored number sequences and a log-linear transformation of at least one of the representation of the stored number sequences by applying a linear or log-linear transformation to a random position of the stored number sequence and comparing the result of the linear or log-linear transformation to a corresponding position of the input number sequence, wherein a match comprises a representation of the stored number sequence passing the linear transformation test;

determining, by performing the constant multiple test, whether the input number sequence comprises a constant multiple of at least one of the representation of the stored number sequences, wherein a match comprises a representation of the stored number sequence passing the constant multiple test;

determining, by performing the constant multiple of a product test, whether the input number sequence comprises a constant multiple of a product of at least one representation of the stored number sequences, wherein a match comprises a representation of the stored number sequence passing the constant multiple of a product test;

determining, by performing the constant multiple of a sum test, whether the input number sequence comprises a constant multiple of a sum of at least one representation of the stored number sequences, wherein a match comprises a representation of the stored number sequence passing the constant multiple of a sum test; and

iteratively performing the ascertaining a match for each of the representation of the stored number sequences until a match is found, the match representing a stored number sequence that corresponds to at least a portion of a specialized predictive cost model for the atomic service and providing the at least a portion of a specialized predictive cost model to a user; and

in the event a match is not found, adding the input number sequence to the library of stored number sequences.

2. The method according to claim 1, wherein said ascertaining comprises mathematically comparing the set of coefficients to the representation of stored number sequences.

3. The method according to claim 2, wherein said determining of a set of coefficients comprises determining a compressed representative sequence pattern for the input number sequence.

4. The method according to claim 1, wherein said ascertaining comprises applying at least one test to determine whether the set of coefficients identifies at least a portion of a stored number sequence as matching the entire input number sequence.

5. The method according to claim 4, wherein:

said accessing comprises accessing a first library; and

said method comprises, in response to a failed matching test with respect to the first library;

accessing a second library of stored number sequences; and

testing whether the input number sequence matches a representation of the stored number sequences of the second library.

6. The method according to claim 5, wherein said testing comprises applying a linear equivalence test.

7. The method according to claim 5, comprising adding the input number sequence to the second library in response to a failed matching test with respect to the second library.

8. The method according to claim 1, wherein said determining of a set of coefficients comprises determining a set of coefficients with respect to at least one predetermined position in the input number sequence.

9. The method according to claim 8, wherein:

the at least one predetermined position comprises at least one initial position; and

said using of the set of coefficients comprises applying at least one test to the at least one initial position.

10. The method according to claim 9, wherein:

the at least one predetermined position comprises at least one random position different from the at least one initial position; and

said ascertaining comprises applying at least one test to the at least one random position.

11. The method according to claim 10, wherein said ascertaining comprises applying at least one test to all remaining positions in the input sequence in response to a successful matching test with respect to the at least one random position.

12. The method according to claim 1, wherein said ascertaining comprises at least one of:

testing whether at least one element of the input number sequence is a constant multiple of at least one of;

an arithmetic pattern, and an exponential pattern;

testing whether at least one element of the input number sequence is a constant multiple of a product of an arithmetic pattern and an exponential pattern; and

testing whether at least one element of the input number sequence is a constant multiple of a sum of an arithmetic pattern and an exponential pattern.

13. The method according to claim 12, wherein said ascertaining comprises all of:

said testing of whether at least one element of the input number sequence is a constant multiple of at least one of;

an arithmetic pattern, and an exponential pattern;

said testing of whether at least one element of the input number sequence is a constant multiple of a product of an arithmetic pattern and an exponential pattern; and

said testing of whether at least one element of the input number sequence is a constant multiple of a sum of an arithmetic pattern and an exponential pattern.

14. The method according to claim 12, wherein said ascertaining comprises, in sequence:

said testing of whether at least one element of the input number sequence is a constant multiple of at least one of;

an arithmetic pattern, and an exponential pattern;

thereafter performing said testing of whether at least one element of the input number sequence is a constant multiple of a product of an arithmetic pattern and an exponential pattern; and

thereafter performing said testing of whether at least one element of the input number sequence is a constant multiple of a sum of an arithmetic pattern and an exponential pattern.

15. An apparatus providing a compressed representation of a number sequence, said apparatus comprising:

at least one processor; and

a computer readable storage medium having computer readable program code embodied therewith and executable by the at least one processor, the computer readable program code comprising;

computer readable program code configured to receive an input number sequence representing an atomic service having a predetermined duration, wherein the input number sequence comprises a plurality of elements, wherein a number of the plurality of elements corresponds to a number of units of time within the predetermined duration represented as an array;

computer readable program code configured to determine a set of coefficients describing the input number sequence, via solving at least one algebraic equation, the at least one algebraic equation comprising at least one of;

an arithmetic equation, and an exponential equation;

computer readable program code configured to access a library of stored number sequences, the number sequences comprising at least one of;

arithmetic number sequences, and exponential number sequences;

computer readable program code configured to determine a representation of the stored number sequences;

computer readable program code configured to ascertain a match of the set of coefficients with respect to the representation of the stored number sequences, wherein the ascertaining a match is performed by partitioning the representation of the stored number sequences into equivalence sets by performing a linear transformation test, a constant multiple test, a constant multiple of a product test, and a constant multiple of sum test on the input number sequence to reduce a number of stored number sequences to be considered when ascertaining a match and increasing a speed for ascertaining a match;

the ascertaining a match comprising;

determining, by performing a linear transformation test, whether the input number sequence is at least one of;

a linear transformation of at least one of the representation of the stored number sequences and a log-linear transformation of at least one of the representation of the stored number sequences by applying a linear or log-linear transformation to a random position of the stored number sequence and comparing the result of the linear or log-linear transformation to a corresponding position of the input number sequence, wherein a match comprises a representation of the stored number sequence passing the linear transformation test;

determining, by performing a constant multiple test, whether the input number sequence comprises a constant multiple of at least one of the representation of the stored number sequences, wherein a match comprises a representation of the stored number sequence passing the constant multiple test;

determining, by performing a constant multiple of a product test, whether the input number sequence comprises a constant multiple of a product of at least one representation of the stored number sequences, wherein a match comprises a representation of the stored number sequence passing the constant multiple of a product test;

determining, by performing a constant multiple of a sum test, whether the input number sequence comprises a constant multiple of a sum of at least one representation of the stored number sequences, wherein a match comprises a representation of the stored number sequence passing the constant multiple of a sum test; and

computer readable program code configured to iteratively perform the ascertaining a match for each of the representation of the stored number sequences until a match is found, the match representing a stored number sequence that corresponds to at least a portion of a specialized predictive cost model for the atomic service and providing the at least a portion of a specialized predictive cost model to a user; and

in the event a match is not found, computer readable program code configured to add the input number sequence to the library of stored number sequences.

16. A computer program product for providing a compressed representation of a number sequence, said computer program product comprising:

a non-transitory computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;

computer readable program code configured to receive an input number sequence representing an atomic service having a predetermined duration, wherein the input number sequence comprises a plurality of elements, wherein a number of the plurality of elements corresponds to a number of units of time within the predetermined duration represented as an array;

computer readable program code configured to determine a set of coefficients describing the input number sequence, via solving at least one algebraic equation, the at least one algebraic equation comprising at least one of;

an arithmetic equation, and an exponential equation;

computer readable program code configured to access a library of stored number sequences, the number sequences comprising at least one of;

arithmetic number sequences, and exponential number sequences;

computer readable program code configured to determine a representation of the stored number sequences;

computer readable program code configured to ascertain a match of the set of coefficients with respect to the representation of the stored number sequences, wherein the ascertaining a match is performed by partitioning the representation of the stored number sequences into equivalence sets by performing a linear transformation test, a constant multiple test, a constant multiple of a product test, and a constant multiple of sum test on the input number sequence to reduce a number of stored number sequences to be considered when ascertaining a match and increasing a speed for ascertaining a match;

the ascertaining a match comprising;

determining, by performing a linear transformation test, whether the input number sequence is at least one of;

a linear transformation of at least one of the representation of the stored number sequences and a log-linear transformation of at least one of the representation of the stored number sequences by applying a linear or log-linear transformation to a random position of the stored number sequence and comparing the result of the linear or log-linear transformation to a corresponding position of the input number sequence, wherein a match comprises a representation of the stored number sequence passing the linear transformation test;

determining, by performing a constant multiple test, whether the input number sequence comprises a constant multiple of at least one of the representation of the stored number sequences, wherein a match comprises a representation of the stored number sequence passing the constant multiple test;

determining, by performing a constant multiple of a product test, whether the input number sequence comprises a constant multiple of a product of at least one representation of the stored number sequences, wherein a match comprises a representation of the stored number sequence passing the constant multiple of a product test;

determining, by performing a constant multiple of a sum test, whether the input number sequence comprises a constant multiple of a sum of at least one representation of the stored number sequences, wherein a match comprises a representation of the stored number sequence passing the constant multiple of a sum test; and

computer readable program code configured to iteratively perform the ascertaining a match for each of the representation of the stored number sequences until a match is found, the match representing a stored number sequence that corresponds to at least a portion of a specialized predictive cost model for the atomic service and providing the at least a portion of a specialized predictive cost model to a user; and

in the event a match is not found, computer readable program code configured to add the input number sequence to the library of stored number sequence.

17. The computer program product according to claim 16, wherein said computer readable program code is configured to mathematically compare the set of coefficients to the representation of stored number sequences.

18. A method of finding a succinct representation for an input sequence of numbers, said method comprising:

maintaining a first library of arithmetic and exponential sequences;

receiving an input number sequence, the input number sequence including a plurality of positions and values associated with the positions;

comparing the input number sequence with sequences from the first library;

said comparing comprising;

computing a set of coefficients with respect to values at given positions in the input sequence, via solving at least one algebraic equation selected from the group consisting of;

an arithmetic equation,

an exponential equation,

a sum of an arithmetic equation and an exponential equation,

a product of an arithmetic equation and an exponential equation,

a product of two arithmetic equations, and

a sum of two exponential equations; and

testing whether the set of coefficients describes a sequence set that matches the entire input sequence, wherein the sequence set includes a sequence or combination of sequences from the first library, wherein the testing is performed by partitioning the sequences from the first library into equivalence sets by performing a linear transformation test, a constant multiple test, a constant multiple of a product test, and a constant multiple of sum test on the input number sequence to reduce a number of sequences from the first library to be considered when ascertaining a match and increasing a speed for ascertaining a match;

the testing comprising;

determining, by performing a linear transformation test, whether the input sequence is at least one of;

a linear transformation of at least one of the sequences from the first library and a log-linear transformation of at least one of the representation of the sequences from the first library by applying a linear or log-linear transformation to a random position of the sequences from the first library and comparing the result of the linear or log-linear transformation to a corresponding position of the input sequence, wherein a match comprises a sequence from the first library passing the linear transformation test;

determining, by performing a constant multiple test, whether the input sequence comprises a constant multiple of at least one of the sequences from the first library, wherein a match comprises a sequence from the first library passing the constant multiple test;

determining, by performing a constant multiple of a product test, whether the input sequence comprises a constant multiple of a product of at least one sequence from the first library, wherein a match comprises a sequence from the first library passing the constant multiple of a product test;

determining, by performing a constant multiple of a sum test, whether the input sequence comprises a constant multiple of a sum of at least one sequence from the first library, wherein a match comprises a sequence from the first library passing the constant multiple of a sum test; and

iteratively performing the testing for each of the sequences from the first library until a match is found, the match representing a stored number sequence that corresponds to at least a portion of a specialized predictive cost model for the atomic service and providing the at least a portion of a specialized predictive cost model to a user; and

in the event a match is not found, adding the input sequence to the first library.

19. The method according to claim 18, wherein:

said testing comprises performing a test on a random position outside of the given set of positions with respect to which the coefficients are computed;

said method comprises, in response to a successful test on the random position, thereafter performing the test on all remaining positions of the input number sequence.

20. The method according to claim 18, comprising:

maintaining a second library of sequences; and

ascertaining whether the input number sequence matches, via linear equivalence, a sequence in the second library.

21. The method according to claim 20, comprising, in response to finding no match in the first library or second library, adding the input sequence to the second library.