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(simIterStruct 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
(s, t, lambda)
|
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(simIterAuthors
Andrei Alexandrescu, Don Clugston, Robert Jacques, Ilya Yaroshenko