fuzzyd.core source code

1 module fuzzyd.core;
2 
3 import std.stdio;
4 import std.array;
5 import std.container.rbtree;
6 import std.container.binaryheap;
7 import std.math;
8 import std.conv;
9 import std.uni;
10 import std.algorithm.iteration;
11 
12 alias fuzzyFn = FuzzyResult[]delegate(string);
13 alias bonusFn = double function(Input);
14 
15 private:
16 
17 struct Input
18 {
19     string input;
20     string pattern;
21     dchar i;
22     dchar p;
23     int col;
24     int row;
25     double[][] scoreMatrix;
26 
27     bool isMatch()
28     {
29         return i.toLower == p.toLower;
30     }
31 
32     bool isCaseSensitiveMatch()
33     {
34         return i.isUpper && p.isUpper && isMatch;
35     }
36 }
37 
38 double previousCharBonus(Input input)
39 {
40     return (input.col > 0 && input.row > 0) ? 2.5 * input
41         .scoreMatrix[input.row - 1][input.col - 1] : 0;
42 }
43 
44 double startBonus(Input input)
45 {
46     return (input.col == 0 && input.row == 0) ? 1 : 0;
47 }
48 
49 double caseMatchBonus(Input input)
50 {
51     return input.isCaseSensitiveMatch ? 1.5 : 0;
52 }
53 
54 double wordBoundaryBonus(Input input)
55 {
56     const isInputAt = input.row == 0 || input.row == input.input.length - 1
57         || isWhite(input.input[input.row - 1]) || isWhite(input.input[input.row + 1]);
58     return isInputAt ? 1.2 : 0;
59 }
60 
61 FuzzyResult[] normalize(FuzzyResult[] result)
62 {
63     const maxScore = !result.empty ? result[0].score : 1;
64     for (long i = 0; i < result.length; i++)
65     {
66         result[i].score /= maxScore;
67     }
68     return result;
69 }
70 
71 public:
72 
73 /// fuzzy search result
74 struct FuzzyResult
75 {
76     string value; //// entry. e.g "Documents/foo/bar/"
77     double score; //// similarity metric. (Higher better)
78     RedBlackTree!(int, "a < b", false) matches; //// index of matched characters.
79 }
80 
81 /**
82  * Fuzzy search
83  * Params:
84  *   db = Array of string containing the search list.
85  * Examples:
86  * --------------------
87  * fuzzy(["foo", "bar", "baz"])("br");
88  * // => [FuzzyResult("bar", 1, RedBlackTree([0, 2])), FuzzyResult("baz", 0.592593, RedBlackTree([0])), FuzzyResult("foo", 0, RedBlackTree([]))]
89  * --------------------
90  */
91 fuzzyFn fuzzy(string[] db)
92 {
93 
94     bonusFn[] bonusFns = [
95         &previousCharBonus, &startBonus, &caseMatchBonus, &wordBoundaryBonus
96     ];
97 
98     double charScore(Input input)
99     {
100         return input.isMatch ? reduce!((acc, f) => acc + f(input))(1.0, bonusFns) : 0;
101     }
102 
103     FuzzyResult score(string input, string pattern)
104     {
105         double score = 0;
106         double simpleMatchScore = 0;
107         double[][] scoreMatrix = new double[][](input.length, pattern.length);
108         auto matches = redBlackTree!int();
109 
110         int row, col;
111         foreach (p; pattern.byCodePoint)
112         {
113             row = 0;
114             foreach (i; input.byCodePoint)
115             {
116                 const charScore = charScore(Input(input, pattern, i, p, col, row, scoreMatrix));
117                 if (charScore > 0)
118                     matches.insert(row);
119                 if (charScore is 1.0)
120                     simpleMatchScore += 1;
121                 else
122                     score += charScore;
123                 scoreMatrix[row][col] = charScore;
124                 row++;
125             }
126             col++;
127         }
128 
129         const totalScore = score + (simpleMatchScore / 2.0);
130         return FuzzyResult(input, totalScore, matches);
131     }
132 
133     FuzzyResult[] search(string pattern)
134     {
135         auto maxpq = BinaryHeap!(FuzzyResult[], "a.score < b.score")(new FuzzyResult[db.length], 0);
136         foreach (e; db)
137         {
138             maxpq.insert(score(e, pattern));
139         }
140         return normalize(maxpq.array());
141     }
142 
143     return &search;
144 }