// Copyright 2019 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "chromeos/ash/components/string_matching/fuzzy_tokenized_string_match.h"
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iterator>
#include <optional>
#include <set>
#include <string>
#include <vector>
#include "base/i18n/case_conversion.h"
#include "base/strings/strcat.h"
#include "base/strings/string_util.h"
#include "chromeos/ash/components/string_matching/acronym_matcher.h"
#include "chromeos/ash/components/string_matching/diacritic_utils.h"
#include "chromeos/ash/components/string_matching/prefix_matcher.h"
#include "chromeos/ash/components/string_matching/sequence_matcher.h"
namespace ash::string_matching {
namespace {
using Hits = FuzzyTokenizedStringMatch::Hits;
constexpr double kPartialMatchPenaltyRate = 0.9;
constexpr double kMinScore = 0.0;
constexpr double kMaxScore = 1.0;
// The maximum supported size for a prefix matching scoring boost.
constexpr size_t kMaxBoostSize = 2;
// The scale ratio for non exact matching results.
constexpr double kNonExactMatchScaleRatio = 0.97;
// Returns sorted tokens from a TokenizedString.
std::vector<std::u16string> ProcessAndSort(const TokenizedString& text) {
std::vector<std::u16string> result;
for (const auto& token : text.tokens()) {
result.emplace_back(token);
}
std::sort(result.begin(), result.end());
return result;
}
double ScaledRelevance(const double relevance) {
return 1.0 - std::pow(0.5, relevance);
}
} // namespace
FuzzyTokenizedStringMatch::~FuzzyTokenizedStringMatch() = default;
FuzzyTokenizedStringMatch::FuzzyTokenizedStringMatch() = default;
double FuzzyTokenizedStringMatch::TokenSetRatio(const TokenizedString& query,
const TokenizedString& text,
bool partial) {
std::set<std::u16string> query_token(query.tokens().begin(),
query.tokens().end());
std::set<std::u16string> text_token(text.tokens().begin(),
text.tokens().end());
std::vector<std::u16string> intersection;
std::vector<std::u16string> query_diff_text;
std::vector<std::u16string> text_diff_query;
// Find the set intersection and the set differences between two sets of
// tokens.
std::set_intersection(query_token.begin(), query_token.end(),
text_token.begin(), text_token.end(),
std::back_inserter(intersection));
std::set_difference(query_token.begin(), query_token.end(),
text_token.begin(), text_token.end(),
std::back_inserter(query_diff_text));
std::set_difference(text_token.begin(), text_token.end(), query_token.begin(),
query_token.end(), std::back_inserter(text_diff_query));
const std::u16string intersection_string =
base::JoinString(intersection, u" ");
const std::u16string query_rewritten =
intersection.empty()
? base::JoinString(query_diff_text, u" ")
: base::StrCat({intersection_string, u" ",
base::JoinString(query_diff_text, u" ")});
const std::u16string text_rewritten =
intersection.empty()
? base::JoinString(text_diff_query, u" ")
: base::StrCat({intersection_string, u" ",
base::JoinString(text_diff_query, u" ")});
if (partial) {
return std::max({PartialRatio(intersection_string, query_rewritten),
PartialRatio(intersection_string, text_rewritten),
PartialRatio(query_rewritten, text_rewritten)});
}
return std::max(
{SequenceMatcher(intersection_string, query_rewritten).Ratio(),
SequenceMatcher(intersection_string, text_rewritten).Ratio(),
SequenceMatcher(query_rewritten, text_rewritten).Ratio()});
}
double FuzzyTokenizedStringMatch::TokenSortRatio(const TokenizedString& query,
const TokenizedString& text,
bool partial) {
const std::u16string query_sorted =
base::JoinString(ProcessAndSort(query), u" ");
const std::u16string text_sorted =
base::JoinString(ProcessAndSort(text), u" ");
if (partial) {
return PartialRatio(query_sorted, text_sorted);
}
return SequenceMatcher(query_sorted, text_sorted).Ratio();
}
double FuzzyTokenizedStringMatch::PartialRatio(const std::u16string& query,
const std::u16string& text) {
if (query.empty() || text.empty()) {
return kMinScore;
}
std::u16string shorter = query;
std::u16string longer = text;
if (shorter.size() > longer.size()) {
shorter = text;
longer = query;
}
const auto matching_blocks =
SequenceMatcher(shorter, longer).GetMatchingBlocks();
double partial_ratio = 0;
for (const auto& block : matching_blocks) {
const int long_start =
block.pos_second_string > block.pos_first_string
? block.pos_second_string - block.pos_first_string
: 0;
// Penalizes the match if it is not close to the beginning of a token.
int current = long_start - 1;
while (current >= 0 &&
!base::EqualsCaseInsensitiveASCII(longer.substr(current, 1), u" ")) {
current--;
}
const double penalty =
std::pow(kPartialMatchPenaltyRate, long_start - current - 1);
// TODO(crbug.com/40638914): currently this part re-calculate the ratio for
// every pair. Improve this to reduce latency.
partial_ratio = std::max(
partial_ratio,
SequenceMatcher(shorter, longer.substr(long_start, shorter.size()))
.Ratio() *
penalty);
if (partial_ratio > 0.995) {
return kMaxScore;
}
}
return partial_ratio;
}
double FuzzyTokenizedStringMatch::WeightedRatio(const TokenizedString& query,
const TokenizedString& text) {
// All token based comparisons are scaled by 0.95 (on top of any partial
// scalars), as per original implementation:
// https://github.com/seatgeek/fuzzywuzzy/blob/af443f918eebbccff840b86fa606ac150563f466/fuzzywuzzy/fuzz.py#L245
const double unbase_scale = 0.95;
// Since query.text() and text.text() is not normalized, we use query.tokens()
// and text.tokens() instead.
const std::u16string query_normalized(base::JoinString(query.tokens(), u" "));
const std::u16string text_normalized(base::JoinString(text.tokens(), u" "));
std::vector<double> weighted_ratios;
weighted_ratios.emplace_back(
SequenceMatcher(query_normalized, text_normalized)
.Ratio(/*text_length_agnostic=*/true));
const double length_ratio =
static_cast<double>(
std::max(query_normalized.size(), text_normalized.size())) /
std::min(query_normalized.size(), text_normalized.size());
// Use partial if two strings are quite different in sizes.
const bool use_partial = length_ratio >= 1.5;
double length_ratio_scale = 1;
if (use_partial) {
// TODO(crbug.com/1336160): Consider scaling |partial_scale| smoothly with
// |length_ratio|, instead of using a step function.
//
// If one string is much much shorter than the other, set |partial_scale| to
// be 0.6, otherwise set it to be 0.9.
length_ratio_scale = length_ratio > 8 ? 0.6 : 0.9;
weighted_ratios.emplace_back(
PartialRatio(query_normalized, text_normalized) * length_ratio_scale);
}
weighted_ratios.emplace_back(TokenSortRatio(query, text, use_partial) *
unbase_scale * length_ratio_scale);
// Do not use partial match for token set because the match between the
// intersection string and query/text rewrites will always return an extremely
// high value.
weighted_ratios.emplace_back(TokenSetRatio(query, text, false /*partial*/) *
unbase_scale * length_ratio_scale);
// Return the maximum of all included weighted ratios
return *std::max_element(weighted_ratios.begin(), weighted_ratios.end());
}
double FuzzyTokenizedStringMatch::PrefixMatcher(const TokenizedString& query,
const TokenizedString& text) {
string_matching::PrefixMatcher match(query, text);
match.Match();
return ScaledRelevance(match.relevance());
}
double FuzzyTokenizedStringMatch::AcronymMatcher(const TokenizedString& query,
const TokenizedString& text) {
string_matching::AcronymMatcher match(query, text);
const double relevance = match.CalculateRelevance();
return ScaledRelevance(relevance);
}
double FuzzyTokenizedStringMatch::PrefixMatcher(
const TokenizedString& query,
const TokenizedString& text,
std::vector<Hits>& hits_vector) {
string_matching::PrefixMatcher match(query, text);
match.Match();
hits_vector.emplace_back(match.hits());
return ScaledRelevance(match.relevance());
}
double FuzzyTokenizedStringMatch::AcronymMatcher(
const TokenizedString& query,
const TokenizedString& text,
std::vector<Hits>& hits_vector) {
string_matching::AcronymMatcher match(query, text);
const double relevance = match.CalculateRelevance();
hits_vector.emplace_back(match.hits());
return ScaledRelevance(relevance);
}
double FuzzyTokenizedStringMatch::Relevance(const TokenizedString& query_input,
const TokenizedString& text_input,
bool use_weighted_ratio,
bool strip_diacritics,
bool use_acronym_matcher) {
// If the query is much longer than the text then it's often not a match.
if (query_input.text().size() >= text_input.text().size() * 2) {
return 0.0;
}
std::optional<TokenizedString> stripped_query;
std::optional<TokenizedString> stripped_text;
if (strip_diacritics) {
stripped_query.emplace(RemoveDiacritics(query_input.text()));
stripped_text.emplace(RemoveDiacritics(text_input.text()));
}
const TokenizedString& query =
strip_diacritics ? stripped_query.value() : query_input;
const TokenizedString& text =
strip_diacritics ? stripped_text.value() : text_input;
// If there is an exact match, relevance will be 1.0 and there is only 1
// hit that is the entire text/query.
const auto& query_text = query.text();
const auto& text_text = text.text();
const auto query_size = query_text.size();
const auto text_size = text_text.size();
if (query_size > 0 && query_size == text_size &&
base::EqualsCaseInsensitiveASCII(query_text, text_text)) {
hits_.emplace_back(0, query_size);
return 1.0;
}
// The |relevances| stores the |relevance_scores| calculated from different
// string matching methods. The highest result among them will be returned.
std::vector<double> relevances;
// The |hits_vector| stores the |hits| calculated from different string
// matching methods. The final selected instance corresponds to the hits
// generated by the matching algorithm which yielded the highest relevance
// score. The final selected instance will be assigned to |hits_| then.
std::vector<Hits> hits_vector;
double prefix_score = PrefixMatcher(query, text, hits_vector);
// A scoring boost for short prefix matching queries.
if (query_size <= kMaxBoostSize && prefix_score > kMinScore) {
prefix_score = std::min(
1.0, prefix_score + 2.0 / (query_size * (query_size + text_size)));
}
relevances.emplace_back(prefix_score);
// Find hits using SequenceMatcher on original query and text.
Hits sequence_hits;
size_t match_size = 0;
for (const auto& match :
SequenceMatcher(query_text, text_text).GetMatchingBlocks()) {
if (match.length > 0) {
match_size += match.length;
sequence_hits.emplace_back(match.pos_second_string,
match.pos_second_string + match.length);
}
}
hits_vector.emplace_back(sequence_hits);
relevances.emplace_back(use_weighted_ratio
? WeightedRatio(query, text)
: SequenceMatcher(base::i18n::ToLower(query_text),
base::i18n::ToLower(text_text))
.Ratio(/*text_length_agnostic=*/true));
if (use_acronym_matcher) {
relevances.emplace_back(AcronymMatcher(query, text, hits_vector));
}
size_t best_match_pos =
std::max_element(relevances.begin(), relevances.end()) -
relevances.begin();
hits_ = hits_vector[best_match_pos];
return match_size == text_size
? relevances[best_match_pos]
: relevances[best_match_pos] * kNonExactMatchScaleRatio;
}
} // namespace ash::string_matching
Codebase Browser
chromium