std.numeric.GapWeightedSimilarityIncremental/gapWeightedSimilarityIncremental
- multiple declarations
Function gapWeightedSimilarityIncremental
Similar to gapWeightedSimilarity
, just works in an incremental
manner by first revealing the matches of length 1, then gapped matches
of length 2, and so on. The memory requirement is Ο(s
). The time complexity is Ο(s
) time
for computing each step. Continuing on the previous example:
GapWeightedSimilarityIncremental!(R,F) gapWeightedSimilarityIncremental(R, F)
(
R r1,
R r2,
F penalty
);
The implementation is based on the pseudocode in Fig. 4 of the paper "Efficient Computation of Gapped Substring Kernels on Large Alphabets" by Rousu et al., with additional algorithmic and systems-level optimizations.
Example
string[] s = ["Hello", "brave", "new", "world"];
string[] t = ["Hello", "new", "world"];
auto simIter = gapWeightedSimilarityIncremental(s, t, 1.0);
assert(simIter .front == 3); // three 1-length matches
simIter .popFront();
assert(simIter .front == 3); // three 2-length matches
simIter .popFront();
assert(simIter .front == 1); // one 3-length match
simIter .popFront();
assert(simIter .empty); // no more match
Struct GapWeightedSimilarityIncremental
Similar to gapWeightedSimilarity
, just works in an incremental
manner by first revealing the matches of length 1, then gapped matches
of length 2, and so on. The memory requirement is Ο(s
). The time complexity is Ο(s
) time
for computing each step. Continuing on the previous example:
struct GapWeightedSimilarityIncremental(Range, F)
if (isRandomAccessRange!Range && hasLength!Range);
The implementation is based on the pseudocode in Fig. 4 of the paper "Efficient Computation of Gapped Substring Kernels on Large Alphabets" by Rousu et al., with additional algorithmic and systems-level optimizations.
Constructors
Name | Description |
---|---|
this
|
Constructs an object given two ranges s and t and a penalty
lambda . Constructor completes in Ο(s )
time and computes all matches of length 1.
|
Properties
Name | Type | Description |
---|---|---|
empty [get]
|
bool | |
front [get]
|
F |
Methods
Name | Description |
---|---|
opSlice
|
|
popFront
|
Computes the match of the popFront length. Completes in Ο(s ) time.
|
Example
string[] s = ["Hello", "brave", "new", "world"];
string[] t = ["Hello", "new", "world"];
auto simIter = gapWeightedSimilarityIncremental(s, t, 1.0);
assert(simIter .front == 3); // three 1-length matches
simIter .popFront();
assert(simIter .front == 3); // three 2-length matches
simIter .popFront();
assert(simIter .front == 1); // one 3-length match
simIter .popFront();
assert(simIter .empty); // no more match
Authors
Andrei Alexandrescu, Don Clugston, Robert Jacques, Ilya Yaroshenko