View source code
Display the source code in std/numeric.d from which this page was generated on github.
Report a bug
If you spot a problem with this page, click here to create a Bugzilla issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone.

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.length * t.length). The time complexity is Ο(s.length * t.length) 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.length * t.length). The time complexity is Ο(s.length * t.length) 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

NameDescription
this Constructs an object given two ranges s and t and a penalty lambda. Constructor completes in Ο(s.length * t.length) time and computes all matches of length 1.

Properties

NameTypeDescription
empty[get] bool
front[get] F

Methods

NameDescription
opSlice
popFront Computes the match of the popFront length. Completes in Ο(s.length * t.length) 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

License

Boost License 1.0.