From eb5ca1125ba043fb83c3a5ae8182ec48aff85c1b Mon Sep 17 00:00:00 2001 From: kotontrion Date: Fri, 11 Oct 2024 11:22:26 +0200 Subject: apps: better fuzzy search algorithm --- lib/apps/fuzzy.vala | 75 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 75 insertions(+) create mode 100644 lib/apps/fuzzy.vala (limited to 'lib/apps/fuzzy.vala') diff --git a/lib/apps/fuzzy.vala b/lib/apps/fuzzy.vala new file mode 100644 index 0000000..d6dac3d --- /dev/null +++ b/lib/apps/fuzzy.vala @@ -0,0 +1,75 @@ + +namespace AstalApps { + + private int max(int a, int b) { + return a > b ? a : b; + } + + public int fuzzy_match_string(string pattern, string str) { + const int unmatched_letter_penalty = -1; + int score = 100; + + if (pattern.length == 0) return score; + if (str.length < pattern.length) return int.MIN; + + score += unmatched_letter_penalty * (str.length - pattern.length); + score = fuzzy_match_recurse(pattern, str, score, true); + + return score; + } + + private int fuzzy_match_recurse(string pattern, string str, int score, bool first_char) { + if (pattern.length == 0) return score; + + int match_idx = 0; + int offset = 0; + unichar search = pattern.casefold().get_char(0); + int best_score = int.MIN; + + while ((match_idx = str.casefold().substring(offset).index_of_char(search)) >= 0) { + offset += match_idx; + int subscore = fuzzy_match_recurse( + pattern.substring(1), + str.substring(offset + 1), + compute_score(offset, first_char, str, offset), false); + best_score = max(best_score, subscore); + offset++; + } + + + if (best_score == int.MIN) return int.MIN; + return score + best_score; + } + + private int compute_score(int jump, bool first_char, string match, int idx) { + const int adjacency_bonus = 15; + const int separator_bonus = 30; + const int camel_bonus = 30; + const int first_letter_bonus = 15; + const int leading_letter_penalty = -5; + const int max_leading_letter_penalty = -15; + + int score = 0; + + if (!first_char && jump == 0) { + score += adjacency_bonus; + } + if (!first_char || jump > 0) { + if (match[idx].isupper() && match[idx-1].islower()) { + score += camel_bonus; + } + if (match[idx].isalnum() && !match[idx-1].isalnum()) { + score += separator_bonus; + } + } + if (first_char && jump == 0) { + score += first_letter_bonus; + } + if (first_char) { + score += max(leading_letter_penalty * jump, max_leading_letter_penalty); + } + + return score; + } + +} -- cgit v1.2.3 From 856f6d06464f5ced12be8dd1a288daccda44c3e5 Mon Sep 17 00:00:00 2001 From: kotontrion Date: Sun, 13 Oct 2024 08:40:10 +0200 Subject: apps: fix style --- lib/apps/fuzzy.vala | 112 ++++++++++++++++++++++++++-------------------------- 1 file changed, 55 insertions(+), 57 deletions(-) (limited to 'lib/apps/fuzzy.vala') diff --git a/lib/apps/fuzzy.vala b/lib/apps/fuzzy.vala index d6dac3d..f93b2eb 100644 --- a/lib/apps/fuzzy.vala +++ b/lib/apps/fuzzy.vala @@ -1,75 +1,73 @@ namespace AstalApps { - private int max(int a, int b) { - return a > b ? a : b; - } +private int max(int a, int b) { + return a > b ? a : b; +} - public int fuzzy_match_string(string pattern, string str) { - const int unmatched_letter_penalty = -1; - int score = 100; +public int fuzzy_match_string(string pattern, string str) { + const int unmatched_letter_penalty = -1; + int score = 100; - if (pattern.length == 0) return score; - if (str.length < pattern.length) return int.MIN; + if (pattern.length == 0) return score; + if (str.length < pattern.length) return int.MIN; - score += unmatched_letter_penalty * (str.length - pattern.length); - score = fuzzy_match_recurse(pattern, str, score, true); + score += unmatched_letter_penalty * (str.length - pattern.length); + score = fuzzy_match_recurse(pattern, str, score, true); - return score; - } + return score; +} - private int fuzzy_match_recurse(string pattern, string str, int score, bool first_char) { - if (pattern.length == 0) return score; +private int fuzzy_match_recurse(string pattern, string str, int score, bool first_char) { + if (pattern.length == 0) return score; + + int match_idx = 0; + int offset = 0; + unichar search = pattern.casefold().get_char(0); + int best_score = int.MIN; + + while ((match_idx = str.casefold().substring(offset).index_of_char(search)) >= 0) { + offset += match_idx; + int subscore = fuzzy_match_recurse( + pattern.substring(1), + str.substring(offset + 1), + compute_score(offset, first_char, str, offset), false); + best_score = max(best_score, subscore); + offset++; + } - int match_idx = 0; - int offset = 0; - unichar search = pattern.casefold().get_char(0); - int best_score = int.MIN; + if (best_score == int.MIN) return int.MIN; + return score + best_score; +} - while ((match_idx = str.casefold().substring(offset).index_of_char(search)) >= 0) { - offset += match_idx; - int subscore = fuzzy_match_recurse( - pattern.substring(1), - str.substring(offset + 1), - compute_score(offset, first_char, str, offset), false); - best_score = max(best_score, subscore); - offset++; - } +private int compute_score(int jump, bool first_char, string match, int idx) { + const int adjacency_bonus = 15; + const int separator_bonus = 30; + const int camel_bonus = 30; + const int first_letter_bonus = 15; + const int leading_letter_penalty = -5; + const int max_leading_letter_penalty = -15; + int score = 0; - if (best_score == int.MIN) return int.MIN; - return score + best_score; + if (!first_char && jump == 0) { + score += adjacency_bonus; } - - private int compute_score(int jump, bool first_char, string match, int idx) { - const int adjacency_bonus = 15; - const int separator_bonus = 30; - const int camel_bonus = 30; - const int first_letter_bonus = 15; - const int leading_letter_penalty = -5; - const int max_leading_letter_penalty = -15; - - int score = 0; - - if (!first_char && jump == 0) { - score += adjacency_bonus; - } - if (!first_char || jump > 0) { - if (match[idx].isupper() && match[idx-1].islower()) { - score += camel_bonus; - } - if (match[idx].isalnum() && !match[idx-1].isalnum()) { - score += separator_bonus; - } - } - if (first_char && jump == 0) { - score += first_letter_bonus; + if (!first_char || jump > 0) { + if (match[idx].isupper() && match[idx-1].islower()) { + score += camel_bonus; } - if (first_char) { - score += max(leading_letter_penalty * jump, max_leading_letter_penalty); + if (match[idx].isalnum() && !match[idx-1].isalnum()) { + score += separator_bonus; } - - return score; + } + if (first_char && jump == 0) { + score += first_letter_bonus; + } + if (first_char) { + score += max(leading_letter_penalty * jump, max_leading_letter_penalty); } + return score; +} } -- cgit v1.2.3 From 0cb8733f31defcf2f7158d23c058fbb92a580215 Mon Sep 17 00:00:00 2001 From: Aylur Date: Tue, 15 Oct 2024 18:58:12 +0000 Subject: docs: apps doc comments docs: apps doc comments --- lib/apps/fuzzy.vala | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) (limited to 'lib/apps/fuzzy.vala') diff --git a/lib/apps/fuzzy.vala b/lib/apps/fuzzy.vala index f93b2eb..97277bd 100644 --- a/lib/apps/fuzzy.vala +++ b/lib/apps/fuzzy.vala @@ -1,11 +1,9 @@ - namespace AstalApps { - private int max(int a, int b) { return a > b ? a : b; } -public int fuzzy_match_string(string pattern, string str) { +private int fuzzy_match_string(string pattern, string str) { const int unmatched_letter_penalty = -1; int score = 100; -- cgit v1.2.3 From 2ad95e05d83a455bb30503ca4ca0aa8356ea5ff7 Mon Sep 17 00:00:00 2001 From: kotontrion Date: Wed, 16 Oct 2024 09:49:37 +0200 Subject: apps: fuzzy: reduce panalty for not matching --- lib/apps/fuzzy.vala | 30 ++++++++++++++++-------------- 1 file changed, 16 insertions(+), 14 deletions(-) (limited to 'lib/apps/fuzzy.vala') diff --git a/lib/apps/fuzzy.vala b/lib/apps/fuzzy.vala index f93b2eb..b77fba7 100644 --- a/lib/apps/fuzzy.vala +++ b/lib/apps/fuzzy.vala @@ -1,10 +1,6 @@ namespace AstalApps { -private int max(int a, int b) { - return a > b ? a : b; -} - public int fuzzy_match_string(string pattern, string str) { const int unmatched_letter_penalty = -1; int score = 100; @@ -12,14 +8,17 @@ public int fuzzy_match_string(string pattern, string str) { if (pattern.length == 0) return score; if (str.length < pattern.length) return int.MIN; + bool found = fuzzy_match_recurse(pattern, str, score, true, out score); score += unmatched_letter_penalty * (str.length - pattern.length); - score = fuzzy_match_recurse(pattern, str, score, true); + + if(!found) score = -10; return score; } -private int fuzzy_match_recurse(string pattern, string str, int score, bool first_char) { - if (pattern.length == 0) return score; +private bool fuzzy_match_recurse(string pattern, string str, int score, bool first_char, out int result) { + result = score; + if (pattern.length == 0) return true; int match_idx = 0; int offset = 0; @@ -28,16 +27,19 @@ private int fuzzy_match_recurse(string pattern, string str, int score, bool firs while ((match_idx = str.casefold().substring(offset).index_of_char(search)) >= 0) { offset += match_idx; - int subscore = fuzzy_match_recurse( + int subscore; + bool found = fuzzy_match_recurse( pattern.substring(1), str.substring(offset + 1), - compute_score(offset, first_char, str, offset), false); - best_score = max(best_score, subscore); + compute_score(offset, first_char, str, offset), false, out subscore); + if(!found) break; + best_score = int.max(best_score, subscore); offset++; } - - if (best_score == int.MIN) return int.MIN; - return score + best_score; + + if (best_score == int.MIN) return false; + result += best_score; + return true; } private int compute_score(int jump, bool first_char, string match, int idx) { @@ -65,7 +67,7 @@ private int compute_score(int jump, bool first_char, string match, int idx) { score += first_letter_bonus; } if (first_char) { - score += max(leading_letter_penalty * jump, max_leading_letter_penalty); + score += int.max(leading_letter_penalty * jump, max_leading_letter_penalty); } return score; -- cgit v1.2.3