// 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 "base/containers/adapters.h"
#include "base/logging.h"
#include "base/strings/stringprintf.h"
#include "base/strings/utf_string_conversions.h"
#include "base/time/time.h"
#include "chromeos/ash/components/string_matching/tokenized_string.h"
#include "testing/gtest/include/gtest/gtest.h"
namespace ash::string_matching {
namespace {
// An upper limit for the purposes of catching regressions. Not for benchmarking
// of typical expected time performance, which is much faster.
constexpr base::TimeDelta kCalculationTimeUpperBound = base::Milliseconds(20);
constexpr double kEps = 1e-5;
constexpr double kCompleteMatchScore = 1.0;
constexpr double kCompleteMismatchScore = 0.0;
// Default parameters.
constexpr bool kUseWeightedRatio = false;
constexpr bool kStripDiacritics = false;
void ExpectAllNearlyEqualTo(const std::vector<double>& scores,
double target_score,
double abs_error = kEps) {
for (const auto score : scores) {
EXPECT_NEAR(target_score, score, abs_error);
}
}
void ExpectAllNearlyEqual(const std::vector<double>& scores,
double abs_error = kEps) {
DCHECK(scores.size() > 0);
ExpectAllNearlyEqualTo(scores, scores[0], abs_error);
}
void ExpectIncreasing(const std::vector<double>& scores,
int start_index,
int end_index,
double epsilon = 0.0) {
if (!end_index) {
end_index = scores.size();
}
for (int i = start_index; i < end_index - 1; ++i) {
EXPECT_LT(scores[i], scores[i + 1] + epsilon);
}
}
// Check that values between `scores[start_index]` (inclusive) and
// `scores[end_index]` (exclusive) are mostly increasing. Allow wiggle room of
// `epsilon` in the definition of "increasing".
//
// Why this is useful:
//
// When the text is long, and depending on the exact input params to
// FuzzyTokenizedStringMatch, we can get variable and sometimes unexpected
// sequences of relevance scores. Scores may or may not be influenced by, e.g.:
// (1) space characters and (2) partial tokens.
void ExpectMostlyIncreasing(const std::vector<double>& scores,
double epsilon,
int start_index = 0,
int end_index = 0) {
ExpectIncreasing(scores, start_index, end_index, epsilon);
}
// Check that values between `scores[start_index]` (inclusive) and
// `scores[end_index]` (exclusive) are strictly increasing.
void ExpectStrictlyIncreasing(const std::vector<double>& scores,
int start_index = 0,
int end_index = 0) {
ExpectIncreasing(scores, start_index, end_index, /*epsilon*/ 0.0);
}
double CalculateRelevance(const std::u16string& query,
const std::u16string& text) {
FuzzyTokenizedStringMatch match;
return match.Relevance(TokenizedString(query), TokenizedString(text),
kUseWeightedRatio);
}
// Return a string formatted for displaying query-text relevance score details.
// Allow specification of query-first/text-first ordering because different
// series of tests will favor different visual display.
std::string FormatRelevanceResult(const std::u16string& query,
const std::u16string& text,
double relevance,
bool query_first = true) {
if (query_first) {
return base::StringPrintf("query: %s, text: %s, relevance: %f",
base::UTF16ToUTF8(query).data(),
base::UTF16ToUTF8(text).data(), relevance);
} else {
return base::StringPrintf("text: %s, query: %s, relevance: %f",
base::UTF16ToUTF8(text).data(),
base::UTF16ToUTF8(query).data(), relevance);
}
}
// Returns a string of |text| marked with the hits using block
// bracket. e.g. text= "Text", hits = [{0,1}], returns "[T]ext".
//
// TODO(crbug.com/1336160): Consider defining it as a |test_util| function as it
// has been used for several unit tests.
std::u16string MatchHit(const std::u16string& text,
const FuzzyTokenizedStringMatch::Hits& hits) {
std::u16string marked = text;
for (const gfx::Range& hit : base::Reversed(hits)) {
marked.insert(hit.end(), 1, u']');
marked.insert(hit.start(), 1, u'[');
}
return marked;
}
} // namespace
class FuzzyTokenizedStringMatchTest : public testing::Test {};
/**********************************************************************
* Benchmarking tests *
**********************************************************************/
// The tests in this section perform benchmarking on the quality of
// relevance scores. See the README for details. These tests are divided into
// two sections:
//
// 1) Abstract test cases - which illustrate our intended string matching
// principles generically.
// 2) Non-abstract test cases - which use real-world examples to:
// a) support the principles in (1).
// b) document bugs.
//
// Both sections will variously cover the following dimensions:
//
// - Special characters:
// - Upper/lower case
// - Numerals
// - Punctuation
// - Typos and misspellings
// - Full vs. partial matches
// - Prefix-related logic
// - Single- vs. multi-token texts
// - Single- vs. multi-token queries
// - Single vs. multiple possible matches
// - Duplicate tokens
//
// Some test cases cover an intersection of multiple dimensions.
//
// Future benchmarking work may cover:
//
// - Special token delimiters
// - Camel case
// - Non-whitespace token delimiters
/**********************************************************************
* Benchmarking section 1 - Abstract test cases *
**********************************************************************/
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkCaseInsensitivity) {
std::u16string text = u"abcde";
std::vector<std::u16string> queries = {u"abcde", u"Abcde", u"aBcDe",
u"ABCDE"};
std::vector<double> scores;
for (const auto& query : queries) {
const double relevance = CalculateRelevance(query, text);
scores.push_back(relevance);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
}
ExpectAllNearlyEqual(scores);
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkNumerals) {
// TODO(crbug.com/1336160): This test is a placeholder to remember to
// consider numerals, and should be refined/removed/expanded as appropriate
// later.
std::u16string text = u"abc123";
std::u16string query = u"abc 123";
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkPunctuation) {
std::u16string text = u"abcde'fg";
std::vector<std::u16string> queries = {u"abcde'fg", u"abcdefg"};
for (const auto& query : queries) {
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
}
// TODO(crbug.com/1336160): Enforce/check that scores are close, after this
// behavior is implemented.
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkCamelCase) {
std::u16string text = u"AbcdeFghIj";
std::vector<std::u16string> queries = {u"AbcdeFghIj", u"abcde fgh ij",
u"abcdefghij", u"abcde fghij"};
std::vector<double> scores;
for (const auto& query : queries) {
const double relevance = CalculateRelevance(query, text);
scores.push_back(relevance);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
}
ExpectAllNearlyEqual(scores, /*abs_error*/ 0.05);
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkCompleteMatchSingleToken) {
// A complete match between text and query should always score very well. Test
// score calculations for pairs of identical strings, for various lengths of
// string.
std::u16string full_string = u"abcdefgh";
for (size_t i = 1; i < full_string.size(); ++i) {
// N.B. The created `substring` is compared to itself, not to `full_string`.
std::u16string substring = full_string.substr(0, i);
const double relevance = CalculateRelevance(substring, substring);
VLOG(1) << FormatRelevanceResult(substring, substring, relevance,
/*query_first*/ false);
EXPECT_NEAR(relevance, kCompleteMatchScore, kEps);
}
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkCompleteMatchMultiToken) {
// A complete match between text and query should always score very well. Test
// score calculations for pairs of identical strings, for various lengths of
// string.
std::u16string full_string = u"ab cdefgh ijk";
for (size_t i = 1; i < full_string.size(); ++i) {
// N.B. The created `substring` is compared to itself, not to `full_string`.
std::u16string substring = full_string.substr(0, i);
const double relevance = CalculateRelevance(substring, substring);
VLOG(1) << FormatRelevanceResult(substring, substring, relevance,
/*query_first*/ false);
EXPECT_NEAR(relevance, kCompleteMatchScore, kEps);
}
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkCompleteNonMatchSingleToken) {
std::u16string full_text = u"abcdefgh";
std::u16string full_query = u"stuvwxyz";
ASSERT_EQ(full_text.size(), full_query.size());
for (size_t i = 1; i < full_text.size(); ++i) {
std::u16string text = full_text.substr(0, i);
std::u16string query = full_query.substr(0, i);
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
EXPECT_NEAR(relevance, kCompleteMismatchScore, kEps);
}
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkCompleteNonMatchMultiToken) {
std::u16string full_text = u"ab cdefgh ijk";
std::u16string full_query = u"pqrstu vw xyz";
ASSERT_EQ(full_text.size(), full_query.size());
for (size_t i = 1; i < full_text.size(); ++i) {
std::u16string text = full_text.substr(0, i);
std::u16string query = full_query.substr(0, i);
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
EXPECT_NEAR(relevance, kCompleteMismatchScore, kEps);
}
}
TEST_F(FuzzyTokenizedStringMatchTest,
BenchmarkVariedLengthUnmatchedTextSingleToken) {
std::u16string full_text = u"abcdefghijklmnop";
const size_t shortest_text_length = 9;
const size_t longest_text_length = full_text.size();
std::vector<std::u16string> queries = {u"abc", u"bcd", u"cde", u"def"};
for (const auto& query : queries) {
// For a fixed query, where the query is a full match to some portion of the
// text, the relevance score should not be influenced by the
// amounts of any remaining unmatched portions of text ("text-length
// agnosticism").
std::vector<double> scores;
for (size_t i = shortest_text_length; i < longest_text_length; ++i) {
std::u16string text = full_text.substr(0, i);
const double relevance = CalculateRelevance(query, text);
scores.push_back(relevance);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ true);
}
ExpectAllNearlyEqual(scores);
}
}
TEST_F(FuzzyTokenizedStringMatchTest,
BenchmarkVariedLengthUnmatchedTextMultiToken) {
std::vector<std::u16string> texts = {u"ab cdefgh", u"ab cdefgh ijk",
u"ab cdefgh ijk lmno",
u"ab cdefgh ijk lmno pqrst"};
std::vector<std::u16string> queries = {
u"ab c", // strict prefix of text
u"cdef", // token prefix of text
u"defg", // token in-fix of text
u"efgh" // token suffix of text
};
for (const auto& query : queries) {
// For a fixed query, where the query is a full match to some portion of the
// text, the relevance score should not be influenced by the
// amounts of any remaining unmatched portions of text ("text-length
// agnosticism").
std::vector<double> scores;
for (const auto& text : texts) {
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ true);
scores.push_back(relevance);
}
ExpectAllNearlyEqual(scores);
}
}
TEST_F(FuzzyTokenizedStringMatchTest,
BenchmarkVariedLengthUnmatchedQuerySingleToken) {
// This test contains the same strings as
// BenchmarkVariedLengthUnmatchedTextSingleToken, with the
// roles of text and query swapped.
std::vector<std::u16string> texts = {u"abc", u"bcd", u"cde", u"def"};
std::u16string full_query = u"abcdefghijklmnop";
const size_t shortest_query_length = 6;
const size_t longest_query_length = full_query.size();
for (const auto& text : texts) {
// Compare a fixed text against a number of queries of differing length,
// where the query is a substring of the text but the query has leftover
// unmatched characters.
for (size_t i = shortest_query_length; i < longest_query_length; ++i) {
std::u16string query = full_query.substr(0, i);
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
}
// TODO(crbug.com/1336160): Decide on how to handle unmatched portions of
// query.
}
}
TEST_F(FuzzyTokenizedStringMatchTest,
BenchmarkVariedLengthUnmatchedQueryMultiToken) {
// This test contains the same strings as
// BenchmarkVariedLengthUnmatchedTextMultiToken, with the
// roles of text and query swapped.
std::vector<std::u16string> texts = {
u"ab c", // strict prefix of query
u"cdef", // token prefix of query
u"defg", // token in-fix of query
u"efgh" // token suffix of query
};
std::vector<std::u16string> queries = {u"ab cdefgh", u"ab cdefgh ijk",
u"ab cdefgh ijk lmno",
u"ab cdefgh ijk lmno pqrst"};
for (const auto& text : texts) {
// Compare a fixed text against a number of queries of differing length,
// where the query is a substring of the text but the query has leftover
// unmathced characters.
for (const auto& query : queries) {
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
}
// TODO(crbug.com/1336160): Decide on how to handle unmatched portions of
// query.
}
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkTokenOrderVariation) {
// Case: Two words.
std::u16string text_two_words = u"abc def";
std::vector<std::u16string> queries_two_words = {u"abc def", u"def abc"};
std::vector<double> scores_query_two_words;
for (const auto& query : queries_two_words) {
const double relevance = CalculateRelevance(query, text_two_words);
scores_query_two_words.push_back(relevance);
VLOG(1) << FormatRelevanceResult(query, text_two_words, relevance,
/*query_first*/ false);
}
ExpectAllNearlyEqual(scores_query_two_words, /*abs_error*/ 0.1);
// Case: Three words.
std::u16string text_three_words = u"abc def ghi";
std::vector<std::u16string> queries_three_words = {
u"abc def ghi", u"abc ghi def", u"def abc ghi",
u"def ghi abc", u"ghi abc def", u"ghi def abc"};
std::vector<double> scores_query_three_words;
for (const auto& query : queries_three_words) {
const double relevance = CalculateRelevance(query, text_three_words);
scores_query_three_words.push_back(relevance);
VLOG(1) << FormatRelevanceResult(query, text_three_words, relevance,
/*query_first*/ false);
}
ExpectAllNearlyEqual(scores_query_three_words, /*abs_error*/ 0.05);
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkTokensPresentInTextButNotQuery) {
std::u16string text = u"abc def ghi";
// Case: multi-token text, single-token query.
std::vector<std::u16string> queries_single_token = {u"abc", u"def", u"ghi"};
std::vector<double> scores_query_single_token;
for (const auto& query : queries_single_token) {
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
scores_query_single_token.push_back(relevance);
}
// There is a score boost in prefix matcher when a matched token is the first
// token of both text and query.
scores_query_single_token[0] -= 0.125;
ExpectAllNearlyEqual(scores_query_single_token, /*abs_error*/ 0.01);
// Case: multi-token text, two-token query.
std::vector<std::u16string> queries_two_tokens = {u"abc def", u"abc ghi",
u"def ghi"};
std::vector<double> scores_query_two_tokens;
for (const auto& query : queries_two_tokens) {
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
scores_query_two_tokens.push_back(relevance);
}
ExpectAllNearlyEqual(scores_query_two_tokens, /*abs_error*/ 0.1);
// TODO(crbug.com/1336160): [Later] Consider a score boost for when a matched
// token is the first token of both text and query.
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkTokensPresentInQueryButNotText) {
// N.B. This test contains the same texts and queries as in
// BenchmarkTokensPresentInTextButNotQuery, with the roles of text and query
// swapped. The expected/desired behavior is quite different, though.
// TODO(crbug.com/1336160): Decide how to handle unmatched query tokens. When
// a text is very short and a query very long, the text and query are probably
// a poor match. However, when both the text and query are long, (e.g. file
// names, keyboard shortcuts), it seems useful to allow for some degree of
// unmatched query tokens.
// TODO(crbug.com/1336160): [Later] Consider a score boost for when a matched
// token is the first token of both text and query.
std::u16string query = u"abc def ghi";
// Case: single-token text.
std::vector<std::u16string> text_single_token = {u"abc", u"def", u"ghi"};
std::vector<double> scores_text_single_token;
for (const auto& text : text_single_token) {
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ true);
scores_text_single_token.push_back(relevance);
}
ExpectAllNearlyEqual(scores_text_single_token);
// Case: two-token text.
std::vector<std::u16string> text_two_tokens = {u"abc def", u"abc ghi",
u"def ghi"};
std::vector<double> scores_text_two_tokens;
for (const auto& text : text_two_tokens) {
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ true);
scores_text_two_tokens.push_back(relevance);
}
ExpectAllNearlyEqual(scores_text_two_tokens, /*abs_error*/ 0.1);
}
TEST_F(FuzzyTokenizedStringMatchTest,
BenchmarkMultipleQueryTokensMapToOneTextToken) {
// This test contains the same strings as
// BenchmarkMultipleTextTokensMapToOneQueryToken, with the
// roles of text and query swapped.
//
// N.B. With the upcoming fuzzy matching v2, supporting flexibility around
// whitespace in this way may turn out to be too onerous. Consider this a
// stretch goal.
// Case 1: single-token text.
std::u16string text1 = u"abcdef";
// A query containing extra whitespace and which is otherwise a good match to
// the text, should score highly. The idea is to treat a small amount of extra
// whitespace as a spelling/grammar mistake.
//
// Here `_ordered` and `_shuffled` refer to the relative positions of the two
// query tokens which map onto the text token "abcdef".
std::vector<std::u16string> queries1_ordered = {u"ab cdef", u"abc def"};
std::vector<double> scores1_ordered;
for (const auto& query : queries1_ordered) {
const double relevance = CalculateRelevance(query, text1);
VLOG(1) << FormatRelevanceResult(query, text1, relevance,
/*query_first*/ false);
scores1_ordered.push_back(relevance);
}
ExpectAllNearlyEqualTo(scores1_ordered, 0.9, /*abs_error*/ 0.1);
// Token-merging should only be considered for consecutive tokens, in line
// with the spelling/grammar mistake philosophy.
std::vector<std::u16string> queries1_shuffled = {u"cdef ab", u"def abc"};
std::vector<double> scores1_shuffled;
for (const auto& query : queries1_shuffled) {
const double relevance = CalculateRelevance(query, text1);
VLOG(1) << FormatRelevanceResult(query, text1, relevance,
/*query_first*/ false);
scores1_shuffled.push_back(relevance);
}
ExpectAllNearlyEqualTo(scores1_shuffled, 0.54, /*abs_error*/ 0.1);
// Case 2: multi-token text.
std::u16string text2 = u"abcdef ghi";
std::vector<std::u16string> queries2_ordered = {
u"ab cdef ghi", u"abc def ghi", u"ghi ab cdef", u"ghi abc def"};
std::vector<double> scores2_ordered;
for (const auto& query : queries2_ordered) {
const double relevance = CalculateRelevance(query, text2);
VLOG(1) << FormatRelevanceResult(query, text2, relevance,
/*query_first*/ false);
scores2_ordered.push_back(relevance);
}
EXPECT_GT(scores2_ordered[0], 0.9);
EXPECT_GT(scores2_ordered[1], 0.9);
// TODO(crbug.com/1336160): Support token-order flexibility to allow the
// following (ish):
//
// ExpectAllNearlyEqualTo(scores2_ordered, 0.9, /*abs_error*/ 0.1);
std::vector<std::u16string> queries2_shuffled = {
u"cdef ab ghi", u"cdef ghi ab", u"def abc ghi", u"ghi def abc"};
std::vector<double> scores2_shuffled;
for (const auto& query : queries2_shuffled) {
const double relevance = CalculateRelevance(query, text2);
VLOG(1) << FormatRelevanceResult(query, text2, relevance,
/*query_first*/ false);
scores2_shuffled.push_back(relevance);
}
ExpectAllNearlyEqualTo(scores2_shuffled, 0.6, /*abs_error*/ 0.25);
}
TEST_F(FuzzyTokenizedStringMatchTest,
BenchmarkMultipleTextTokensMapToOneQueryToken) {
// This test contains the same strings as
// BenchmarkMultipleQueryTokensMapToOneTextToken, with the
// roles of text and query swapped.
//
// N.B. With the upcoming fuzzy matching v2, supporting flexibility around
// whitespace in this way may turn out to be too onerous. Consider this a
// stretch goal.
// Case 1: single-token query.
std::u16string query1 = u"abcdef";
// A text containing extra whitespace and which is otherwise a good match to
// the query, should score highly. The idea is to treat a small amount of
// extra whitespace as a spelling/grammar mistake.
//
// Here `_ordered` and `_shuffled` refer to the relative positions of the two
// text tokens which map onto the query token "abcdef".
std::vector<std::u16string> texts1_ordered = {u"ab cdef", u"abc def"};
std::vector<double> scores1_ordered;
for (const auto& text : texts1_ordered) {
const double relevance = CalculateRelevance(query1, text);
VLOG(1) << FormatRelevanceResult(query1, text, relevance,
/*query_first*/ true);
scores1_ordered.push_back(relevance);
}
ExpectAllNearlyEqualTo(scores1_ordered, 0.9, /*abs_error*/ 0.1);
// Token-merging should only be considered for consecutive tokens, in line
// with the spelling/grammar mistake philosophy.
std::vector<std::u16string> texts1_shuffled = {u"cdef ab", u"def abc"};
std::vector<double> scores1_shuffled;
for (const auto& text : texts1_shuffled) {
const double relevance = CalculateRelevance(query1, text);
VLOG(1) << FormatRelevanceResult(query1, text, relevance,
/*query_first*/ true);
scores1_shuffled.push_back(relevance);
}
ExpectAllNearlyEqualTo(scores1_shuffled, 0.6, /*abs_error*/ 0.2);
// Case 2: multi-token query.
std::u16string query2 = u"abcdef ghi";
std::vector<std::u16string> texts2_ordered = {u"ab cdef ghi", u"abc def ghi",
u"ghi ab cdef", u"ghi abc def"};
std::vector<double> scores2_ordered;
for (const auto& text : texts2_ordered) {
const double relevance = CalculateRelevance(query2, text);
VLOG(1) << FormatRelevanceResult(query2, text, relevance,
/*query_first*/ true);
scores2_ordered.push_back(relevance);
}
EXPECT_GT(scores2_ordered[0], 0.9);
EXPECT_GT(scores2_ordered[1], 0.9);
// TODO(crbug.com/1336160): Support token-order flexibility to allow the
// following (ish):
//
// ExpectAllNearlyEqualTo(scores2_ordered, 0.9, /*abs_error*/ 0.1);
std::vector<std::u16string> texts2_shuffled = {
u"cdef ab ghi", u"cdef ghi ab", u"def abc ghi", u"ghi def abc"};
std::vector<double> scores2_shuffled;
for (const auto& text : texts2_shuffled) {
const double relevance = CalculateRelevance(query2, text);
VLOG(1) << FormatRelevanceResult(query2, text, relevance,
/*query_first*/ true);
scores2_shuffled.push_back(relevance);
}
ExpectAllNearlyEqualTo(scores2_shuffled, 0.6, /*abs_error*/ 0.25);
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkPartialMatchPartialMismatch) {
std::u16string text = u"abcdef";
std::u16string query_full = u"abcdef";
std::u16string query_prefix = u"abc";
std::u16string query_suffix_mismatch = u"abcxyz";
std::u16string query_prefix_mismatch = u"xyzdef";
std::u16string query_suffix_is_text_prefix = u"xyzabc";
std::u16string query_prefix_is_text_suffix = u"defxyz";
const double relevance_query_full = CalculateRelevance(query_full, text);
VLOG(1) << FormatRelevanceResult(query_full, text, relevance_query_full,
/*query_first*/ false);
const double relevance_query_prefix = CalculateRelevance(query_prefix, text);
VLOG(1) << FormatRelevanceResult(query_prefix, text, relevance_query_prefix,
/*query_first*/ false);
const double relevance_query_suffix_mismatch =
CalculateRelevance(query_suffix_mismatch, text);
VLOG(1) << FormatRelevanceResult(query_suffix_mismatch, text,
relevance_query_suffix_mismatch,
/*query_first*/ false);
const double relevance_query_prefix_mismatch =
CalculateRelevance(query_prefix_mismatch, text);
VLOG(1) << FormatRelevanceResult(query_prefix_mismatch, text,
relevance_query_prefix_mismatch,
/*query_first*/ false);
const double relevance_query_suffix_is_text_prefix =
CalculateRelevance(query_suffix_is_text_prefix, text);
VLOG(1) << FormatRelevanceResult(query_suffix_is_text_prefix, text,
relevance_query_suffix_is_text_prefix,
/*query_first*/ false);
const double relevance_query_prefix_is_text_suffix =
CalculateRelevance(query_prefix_is_text_suffix, text);
VLOG(1) << FormatRelevanceResult(query_prefix_is_text_suffix, text,
relevance_query_prefix_is_text_suffix,
/*query_first*/ false);
CHECK_GT(relevance_query_full, relevance_query_prefix);
CHECK_GT(relevance_query_prefix, relevance_query_suffix_mismatch);
CHECK_GT(relevance_query_prefix, relevance_query_prefix_mismatch);
CHECK_GT(relevance_query_prefix, relevance_query_suffix_is_text_prefix);
CHECK_GT(relevance_query_prefix, relevance_query_prefix_is_text_suffix);
// TODO(crbug.com/1336160): Consider the following if/when supported:
//
// CHECK_GT(relevance_query_suffix_mismatch, relevance_query_prefix_mismatch);
// CHECK_GT(relevance_query_suffix_mismatch,
// relevance_query_suffix_is_text_prefix);
}
TEST_F(FuzzyTokenizedStringMatchTest,
BenchmarkPrefixOfVaryingLengthSingleToken) {
std::u16string text = u"abcdefg";
std::u16string query_full = u"abcdefg";
std::vector<double> scores;
for (size_t i = 1; i < text.size(); ++i) {
std::u16string query = text.substr(0, i);
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
scores.push_back(relevance);
}
// Intuitively, it seems desirable that, for a fixed text, the longer the
// prefix match between text and a query, the greater the relevance score
// should be. Check for this behavior here, but revisit the utility of this
// later as it relates to text-length agnosticism.
ExpectStrictlyIncreasing(scores);
}
TEST_F(FuzzyTokenizedStringMatchTest,
BenchmarkPrefixOfVaryingLengthMultiToken) {
std::u16string text = u"ghijkl abcdef";
std::vector<std::u16string> queries = {u"a", u"ab", u"abc",
u"abcd", u"abcde", u"abcdef"};
std::vector<double> scores;
for (const auto& query : queries) {
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
scores.push_back(relevance);
}
// Intuitively, it seems desirable that, for a fixed text, the longer the
// prefix match between text and a query, the greater the relevance score
// should be. Check for this behavior here, but revisit the utility of this
// later as it relates to text-length agnosticism.
ExpectStrictlyIncreasing(scores);
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkPrefixVsNonPrefixSingleToken) {
std::u16string text = u"abcdefg";
std::vector<std::u16string> queries = {u"ab", u"bc", u"cd",
u"de", u"ef", u"fg"};
std::vector<double> scores;
for (const auto& query : queries) {
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
scores.push_back(relevance);
}
// Only query "ab" should benefit from a prefix-related scoring boost, and
// the boost should be fairly high.
const double prefix_score_boost = 0.3;
EXPECT_GT(scores[0], scores[1] + prefix_score_boost);
EXPECT_GT(scores[0], scores[2] + prefix_score_boost);
EXPECT_GT(scores[0], scores[3] + prefix_score_boost);
EXPECT_GT(scores[0], scores[4] + prefix_score_boost);
EXPECT_GT(scores[0], scores[5] + prefix_score_boost);
// TODO(crbug.com/1336160): Consider whether position of match should be
// important when the match does not involve a prefix of the text. For example
// here, is it meaningful or useful for query "bc" to be a better match than
// query "cd"?
}
TEST_F(FuzzyTokenizedStringMatchTest,
BenchmarkPrefixVsNonPrefixForTextAndQuerySingleToken) {
std::u16string text = u"abcdefgh";
// For a fixed length of matched portion between text and query, cover cases
// where the matched portion is:
std::vector<std::u16string> queries = {
u"abcd", // case 0: a text prefix, and query prefix.
u"cdef", // case 1: a text non-prefix, and query prefix.
u"xabcd", // case 2: a text prefix, and query non-prefix.
u"xcdef" // case 3: a text non-prefix, and query non-prefix.
};
// N.B. It isn't possible to have all the queries be the same length while
// also creating matched portions of the same length. So there is some
// necessary overlap of prefix scoring logic with other logic here.
double relevance0 = CalculateRelevance(queries[0], text);
VLOG(1) << FormatRelevanceResult(queries[0], text, relevance0,
/*query_first*/ false);
double relevance1 = CalculateRelevance(queries[1], text);
VLOG(1) << FormatRelevanceResult(queries[1], text, relevance1,
/*query_first*/ false);
double relevance2 = CalculateRelevance(queries[2], text);
VLOG(1) << FormatRelevanceResult(queries[2], text, relevance2,
/*query_first*/ false);
double relevance3 = CalculateRelevance(queries[3], text);
VLOG(1) << FormatRelevanceResult(queries[3], text, relevance3,
/*query_first*/ false);
// Only case 0 should benefit from a prefix-related scoring boost, and
// the boost should be fairly high.
const double prefix_score_boost = 0.25;
EXPECT_GT(relevance0, relevance1 + prefix_score_boost);
EXPECT_GT(relevance0, relevance2 + prefix_score_boost);
EXPECT_GT(relevance0, relevance3 + prefix_score_boost);
// TODO(crbug.com/1336160): Consider whether cases 1, 2, and 3 should have
// some expected ordering. e.g. choose between the following:
//
// A prefix match (for either text or query) provides a boost i.e.:
// R0 > R1, R2 > R3
//
// A prefix score boost is only given in case 0 i.e.:
// R0 > R1 ~= R2 ~= R3
}
TEST_F(FuzzyTokenizedStringMatchTest,
BenchmarkPrefixVsContiguousBlockSingleToken) {
std::u16string text = u"ababc";
std::u16string query = u"abc";
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
// TODO(crbug.com/1336160): Consider having a strong opinion on whether prefix
// matching or longest-contiguous-block matching should take precedence in
// these cases.
//
// Prefix matching:
//
// text: ababc
// query: ab c
//
// Longest-contiguous-block matching:
//
// text: ababc
// query: abc
}
TEST_F(FuzzyTokenizedStringMatchTest,
BenchmarkPrefixVsContiguousBlockMultiToken) {
std::u16string text = u"abxyz wabc";
std::u16string query = u"abc";
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
// See also BenchmarkPrefixVsContiguousBlockSingleToken above, for note on
// prefix matching vs. longest contiguous block matching.
}
TEST_F(FuzzyTokenizedStringMatchTest,
BenchmarkHitsMatchHighestMatchingAlgorithm) {
FuzzyTokenizedStringMatch match;
struct {
const std::u16string text;
const std::u16string query;
const std::u16string expect;
const bool use_acronym_matcher;
} kTestCases[] = {
// Prefix Matcher is favored over Sequence Matcher.
{u"xyzabc abcdef", u"abc", u"xyzabc [abc]def",
/*use_acronym_matcher=*/true},
{u"xyzabc abcdef", u"abc", u"xyzabc [abc]def",
/*use_acronym_matcher=*/false},
// Acronym Matcher is favored over Sequence Matcher.
{u"dabc axyz bxyz cxzy", u"abc", u"dabc [a]xyz [b]xyz [c]xzy",
/*use_acronym_matcher=*/true},
{u"dabc axyz bxyz cxzy", u"abc", u"d[abc] axyz bxyz cxzy",
/*use_acronym_matcher=*/false},
// Prefix Matcher at first token is favored over Acronym Matcher.
{u"abcxyz bxyz cxzy", u"abc", u"[abc]xyz bxyz cxzy",
/*use_acronym_matcher=*/true},
{u"abcxyz bxyz cxzy", u"abc", u"[abc]xyz bxyz cxzy",
/*use_acronym_matcher=*/false},
// Acronym Matcher is favored over Prefix Matcher at non-first token.
{u"def abcxyz bxyz cxzy", u"abc", u"def [a]bcxyz [b]xyz [c]xzy",
/*use_acronym_matcher=*/true},
{u"def abcxyz bxyz cxzy", u"abc", u"def [abc]xyz bxyz cxzy",
/*use_acronym_matcher=*/false},
};
for (auto& test_case : kTestCases) {
const TokenizedString query(test_case.query);
const TokenizedString text(test_case.text);
double relevance =
match.Relevance(query, text, kUseWeightedRatio, kStripDiacritics,
/*use_acronym_matcher=*/test_case.use_acronym_matcher);
VLOG(1) << FormatRelevanceResult(test_case.query, test_case.text, relevance,
/*query_first*/ false);
EXPECT_EQ(test_case.expect, MatchHit(test_case.text, match.hits()));
}
}
TEST_F(FuzzyTokenizedStringMatchTest,
BenchmarkPrefixVariedWordOrderMultiToken) {
std::u16string text = u"abcd efgh ijkl";
std::vector<std::u16string> queries = {u"abcd ef", u"abcd ij", u"efgh ab",
u"efgh ij", u"ijkl ab", u"ijkl ef"};
std::vector<double> scores;
for (const auto& query : queries) {
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
scores.push_back(relevance);
}
// There is a score boost in prefix matcher when a matched token is the first
// token of both text and query.
scores[0] -= 0.04;
scores[1] -= 0.04;
ExpectAllNearlyEqual(scores, /*abs_error*/ 0.01);
}
TEST_F(FuzzyTokenizedStringMatchTest,
BenchmarkPrefixMultipleSameLengthMatchesMultiToken) {
FuzzyTokenizedStringMatch match;
std::u16string text = u"abcde abfgh abijk";
std::u16string query = u"ab";
const double relevance = match.Relevance(
TokenizedString(query), TokenizedString(text), kUseWeightedRatio);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
// Where multiple same-length token prefix matches are possible, prioritize
// the earliest match.
EXPECT_EQ(match.hits().size(), 1u);
EXPECT_EQ(match.hits()[0].start(), 0u);
EXPECT_EQ(match.hits()[0].end(), 2u);
}
TEST_F(FuzzyTokenizedStringMatchTest,
BenchmarkPrefixMultiplePossibleVariedLengthMatchesMultiToken) {
FuzzyTokenizedStringMatch match;
std::u16string text = u"abxyz abcwv abcdt";
std::u16string query = u"abcde";
const double relevance = match.Relevance(
TokenizedString(query), TokenizedString(text), kUseWeightedRatio);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
// Expect a single hit, for the "abcd" of "abcdt".
EXPECT_EQ(match.hits().size(), 1u);
EXPECT_EQ(match.hits()[0].start(), 12u);
EXPECT_EQ(match.hits()[0].end(), 16u);
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkStressTestLongText) {
// Same as BenchmarkStressTestLongQuery, with the roles of text and query
// reversed.
std::u16string text(300, 'a');
std::u16string query_high_match(25, 'a');
std::u16string query_low_match(u"bbbbbcccccbbbbbaaaaabbbbbcccccbbbbb");
std::u16string query_no_match(25, 'b');
std::vector<std::u16string> queries = {query_high_match, query_low_match,
query_no_match};
for (const auto& query : queries) {
base::Time start_time = base::Time::NowFromSystemTime();
const double relevance = CalculateRelevance(query, text);
base::TimeDelta elapsed_time = base::Time::NowFromSystemTime() - start_time;
EXPECT_LT(elapsed_time, kCalculationTimeUpperBound);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
VLOG(1) << "Elapsed time (ms): " << elapsed_time.InMillisecondsF();
}
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkStressTestLongQuery) {
// Same as BenchmarkStressTestLongText, with the roles of text and query
// reversed.
std::u16string query(300, 'a');
std::u16string text_high_match(25, 'a');
std::u16string text_low_match(u"bbbbbcccccbbbbbaaaaabbbbbcccccbbbbb");
std::u16string text_no_match(25, 'b');
std::vector<std::u16string> texts = {text_high_match, text_low_match,
text_no_match};
for (const auto& text : texts) {
base::Time start_time = base::Time::NowFromSystemTime();
const double relevance = CalculateRelevance(query, text);
base::TimeDelta elapsed_time = base::Time::NowFromSystemTime() - start_time;
EXPECT_LT(elapsed_time, kCalculationTimeUpperBound);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ true);
VLOG(1) << "Elapsed time (ms): " << elapsed_time.InMillisecondsF();
}
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkStressTestLongTextLongQuery) {
std::u16string text(300, 'a');
std::u16string query_high_match(300, 'a');
std::u16string query_low_match = std::u16string(140, 'b') +
std::u16string(20, 'a') +
std::u16string(140, 'b');
std::u16string query_no_match(300, 'b');
std::vector<std::u16string> queries = {query_high_match, query_low_match,
query_no_match};
for (const auto& query : queries) {
base::Time start_time = base::Time::NowFromSystemTime();
const double relevance = CalculateRelevance(query, text);
base::TimeDelta elapsed_time = base::Time::NowFromSystemTime() - start_time;
EXPECT_LT(elapsed_time, kCalculationTimeUpperBound);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
VLOG(1) << "Elapsed time (ms): " << elapsed_time.InMillisecondsF();
}
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkStressTestManyTokens) {
std::u16string text =
u"aaa bbb ccc ddd eee fff ggg hhh iii jjj kkk lll mmm nnn ooo ppp qqq "
u"rrr sss ttt uuu vvv www xxx yyy zzz";
std::u16string query =
u"zzz yyy xxx www vvv uuu ttt sss rrr qqq ppp ooo nnn mmm lll kkk jjj "
u"iii hhh ggg fff eee ddd ccc bbb aaa";
base::Time start_time = base::Time::NowFromSystemTime();
const double relevance = CalculateRelevance(query, text);
base::TimeDelta elapsed_time = base::Time::NowFromSystemTime() - start_time;
EXPECT_LT(elapsed_time, kCalculationTimeUpperBound);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
VLOG(1) << "Elapsed time (ms): " << elapsed_time.InMillisecondsF();
}
/**********************************************************************
* Benchmarking section 2 - Non-abstract test cases *
**********************************************************************/
// TODO(crbug.com/40211626): Make matching less permissive where the strings
// are short and the matching is multi-block (e.g. "chat" vs "caret").
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkAppsShortNamesMultiBlock) {
std::u16string query1 = u"chat";
std::vector<std::u16string> texts1 = {u"Chat", u"Caret", u"Calendar",
u"Camera", u"Chrome"};
for (const auto& text : texts1) {
const double relevance = CalculateRelevance(query1, text);
VLOG(1) << FormatRelevanceResult(query1, text, relevance,
/*query_first*/ true);
}
std::u16string query2 = u"ses";
std::vector<std::u16string> texts2 = {u"Sheets", u"Slides"};
for (const auto& text : texts2) {
const double relevance = CalculateRelevance(query2, text);
VLOG(1) << FormatRelevanceResult(query2, text, relevance,
/*query_first*/ true);
}
}
// TODO(crbug.com/40227656): Reduce permissivity currently afforded by block
// matching algorithm.
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkAssistantAndGamesWeather) {
std::u16string query = u"weather";
std::vector<std::u16string> texts = {u"weather", u"War Thunder",
u"Man Eater"};
for (const auto& text : texts) {
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ true);
}
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkChromeMultiBlock) {
std::u16string text = u"Chrome";
// N.B. "c", "ch", "chr", are not multiblock matches to "Chrome", but are
// included for comparison.
std::vector<std::u16string> queries = {u"c", u"ch", u"chr", u"co", u"com",
u"cho", u"che", u"cr", u"cro", u"cre",
u"ho", u"hom", u"hoe", u"roe"};
for (const auto& query : queries) {
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
}
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkChromePrefix) {
std::vector<std::u16string> texts = {u"Chrome", u"Google Chrome"};
std::vector<std::u16string> queries = {u"c", u"ch", u"chr",
u"chro", u"chrom", u"chrome"};
for (const auto& text : texts) {
std::vector<double> scores;
for (const auto& query : queries) {
const double relevance = CalculateRelevance(query, text);
scores.push_back(relevance);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
}
ExpectMostlyIncreasing(scores, /*epsilon=*/0.001);
}
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkChromeTransposition) {
std::u16string text = u"Chrome";
// Single character-pair transpositions.
std::vector<std::u16string> queries = {u"chrome", u"hcrome", u"crhome",
u"chorme", u"chroem"};
for (const auto& query : queries) {
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
}
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkGamesArk) {
std::u16string query = u"ark";
// Intended string matching guidelines for these cases:
// - Favor full token matches over partial token matches.
// - Favor prefix matches over non-prefix matches.
// - Do not penalize for unmatched lengths of text.
std::vector<std::u16string> texts = {u"Pixark", u"LOST ARK",
u"ARK: Survival Evolved"};
std::vector<double> scores;
for (const auto& text : texts) {
const double relevance = CalculateRelevance(query, text);
scores.push_back(relevance);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ true);
}
ExpectStrictlyIncreasing(scores);
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkGamesAssassinsCreed) {
std::u16string text = {u"Assassin's Creed"};
// Variations on punctuation and spelling
std::vector<std::u16string> queries = {
u"assassin", u"assassin'", u"assassin's", u"assassins",
u"assasin", u"assasin's", u"assasins"};
for (const auto& query : queries) {
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
}
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkKeyboardShortcutsScreenshot) {
std::u16string query = u"screenshot";
std::vector<std::u16string> texts = {u"Take fullscreen screenshot",
u"Take partial screenshot/recording",
u"Take screenshot/recording"};
for (const auto& text : texts) {
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ true);
}
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkKeyboardShortcutsDesk) {
std::u16string text = u"Create a new desk";
std::u16string text_lower = u"create a new desk";
std::vector<std::u16string> queries_strict_prefix = {u"crea",
u"creat",
u"create",
u"create ",
u"create a",
u"create a ",
u"create a n",
u"create a ne",
u"create a new",
u"create a new ",
u"create a new d",
u"create a new de",
u"create a new des",
u"create a new desk"};
std::vector<std::u16string> queries_missing_words = {
u"new ", u"desk",
u"new d", u"new de",
u"new des", u"new desk",
u"create d", u"create n",
u"create de", u"create ne",
u"create a d", u"create a de",
u"create new", u"create des",
u"create new ", u"create desk",
u"create a des", u"create new d",
u"create a desk", u"create new de",
u"create new des", u"create new desk",
};
std::vector<double> scores;
for (const auto& query : queries_strict_prefix) {
const double relevance = CalculateRelevance(query, text);
scores.push_back(relevance);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
}
// Allow a flexible (rather than strict) increase in scores.
ExpectMostlyIncreasing(scores, /*epsilon*/ 0.005);
scores.clear();
for (const auto& query : queries_missing_words) {
const double relevance = CalculateRelevance(query, text);
scores.push_back(relevance);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
}
// With word order flexibility, the scores are expected to increase as the
// query length increases.
//
// Allow a flexible (rather than strict) increase in scores.
ExpectMostlyIncreasing(scores, /*epsilon*/ 0.005);
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkKeyboardShortcutsEmojiPicker) {
std::u16string text = u"Open Emoji picker";
std::vector<std::u16string> queries = {u"emoj", u"emoji", u"emoji ",
u"emoji p", u"emoji pi"};
std::vector<double> scores;
for (const auto& query : queries) {
const double relevance = CalculateRelevance(query, text);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
scores.push_back(relevance);
}
ExpectMostlyIncreasing(scores, /*epsilon=*/0.001);
ExpectAllNearlyEqualTo(scores, 0.9, /*abs_error=*/0.1);
}
TEST_F(FuzzyTokenizedStringMatchTest,
BenchmarkKeyboardShortcutsIncognitoWindow) {
std::u16string text = u"Open a new window in incognito mode";
std::vector<std::u16string> queries = {u"new window incognito",
u"new incognito window"};
std::vector<double> scores;
for (const auto& query : queries) {
const double relevance = CalculateRelevance(query, text);
scores.push_back(relevance);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
}
ExpectAllNearlyEqual(scores);
}
TEST_F(FuzzyTokenizedStringMatchTest, BenchmarkSettingsPreferences) {
std::u16string query = u"preferences";
std::vector<std::u16string> texts = {
u"Android preferences", u"Caption preferences", u"System preferences",
u"External storage preferences"};
std::vector<double> scores;
for (const auto& text : texts) {
const double relevance = CalculateRelevance(query, text);
scores.push_back(relevance);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ true);
}
ExpectAllNearlyEqual(scores);
}
/**********************************************************************
* Per-method tests *
**********************************************************************/
// The tests in this section check the functionality of individual class
// methods (as opposed to the score benchmarking performed above).
// TODO(crbug.com/1336160): update the tests once params are consolidated.
TEST_F(FuzzyTokenizedStringMatchTest, PartialRatioTest) {
FuzzyTokenizedStringMatch match;
EXPECT_NEAR(match.PartialRatio(u"abcde", u"ababcXXXbcdeY"), 0.6, 0.1);
EXPECT_NEAR(match.PartialRatio(u"big string", u"strength"), 0.7, 0.1);
EXPECT_EQ(match.PartialRatio(u"abc", u""), 0);
EXPECT_NEAR(match.PartialRatio(u"different in order", u"order text"), 0.6,
0.1);
}
TEST_F(FuzzyTokenizedStringMatchTest, TokenSetRatioTest) {
FuzzyTokenizedStringMatch match;
{
std::u16string query(u"order different in");
std::u16string text(u"text order");
EXPECT_EQ(match.TokenSetRatio(TokenizedString(query), TokenizedString(text),
true),
1);
EXPECT_NEAR(match.TokenSetRatio(TokenizedString(query),
TokenizedString(text), false),
0.6, 0.1);
}
{
std::u16string query(u"short text");
std::u16string text(u"this text is really really really long");
EXPECT_EQ(match.TokenSetRatio(TokenizedString(query), TokenizedString(text),
true),
1);
EXPECT_NEAR(match.TokenSetRatio(TokenizedString(query),
TokenizedString(text), false),
0.5, 0.1);
}
{
std::u16string query(u"common string");
std::u16string text(u"nothing is shared");
EXPECT_NEAR(match.TokenSetRatio(TokenizedString(query),
TokenizedString(text), true),
0.3, 0.1);
EXPECT_NEAR(match.TokenSetRatio(TokenizedString(query),
TokenizedString(text), false),
0.3, 0.1);
}
{
std::u16string query(u"token shared token same shared same");
std::u16string text(u"token shared token text text long");
EXPECT_EQ(match.TokenSetRatio(TokenizedString(query), TokenizedString(text),
true),
1);
EXPECT_NEAR(match.TokenSetRatio(TokenizedString(query),
TokenizedString(text), false),
0.8, 0.1);
}
}
TEST_F(FuzzyTokenizedStringMatchTest, TokenSortRatioTest) {
FuzzyTokenizedStringMatch match;
{
std::u16string query(u"order different in");
std::u16string text(u"text order");
EXPECT_NEAR(match.TokenSortRatio(TokenizedString(query),
TokenizedString(text), true),
0.6, 0.1);
EXPECT_NEAR(match.TokenSortRatio(TokenizedString(query),
TokenizedString(text), false),
0.3, 0.1);
}
{
std::u16string query(u"short text");
std::u16string text(u"this text is really really really long");
EXPECT_EQ(match.TokenSortRatio(TokenizedString(query),
TokenizedString(text), true),
0.5 * std::pow(0.9, 1));
EXPECT_NEAR(match.TokenSortRatio(TokenizedString(query),
TokenizedString(text), false),
0.3, 0.1);
}
{
std::u16string query(u"common string");
std::u16string text(u"nothing is shared");
EXPECT_NEAR(match.TokenSortRatio(TokenizedString(query),
TokenizedString(text), true),
0.3, 0.1);
EXPECT_NEAR(match.TokenSortRatio(TokenizedString(query),
TokenizedString(text), false),
0.3, 0.1);
}
}
TEST_F(FuzzyTokenizedStringMatchTest, WeightedRatio) {
FuzzyTokenizedStringMatch match;
{
std::u16string query(u"anonymous");
std::u16string text(u"famous");
EXPECT_NEAR(
match.WeightedRatio(TokenizedString(query), TokenizedString(text)), 0.6,
0.1);
}
{
std::u16string query(u"Clash.of.clan");
std::u16string text(u"ClashOfTitan");
EXPECT_NEAR(
match.WeightedRatio(TokenizedString(query), TokenizedString(text)), 0.8,
0.1);
}
{
std::u16string query(u"final fantasy");
std::u16string text(u"finalfantasy");
EXPECT_NEAR(
match.WeightedRatio(TokenizedString(query), TokenizedString(text)), 0.9,
0.1);
}
{
std::u16string query(u"short text!!!");
std::u16string text(
u"this sentence is much much much much much longer "
u"than the text before");
EXPECT_NEAR(
match.WeightedRatio(TokenizedString(query), TokenizedString(text)), 0.6,
0.1);
}
}
TEST_F(FuzzyTokenizedStringMatchTest, PrefixMatcherTest) {
{
std::u16string query(u"clas");
std::u16string text(u"Clash of Clan");
EXPECT_NEAR(FuzzyTokenizedStringMatch::PrefixMatcher(TokenizedString(query),
TokenizedString(text)),
0.94, 0.01);
}
{
std::u16string query(u"clash clan");
std::u16string text(u"Clash of Clan");
EXPECT_NEAR(FuzzyTokenizedStringMatch::PrefixMatcher(TokenizedString(query),
TokenizedString(text)),
0.99, 0.01);
}
{
std::u16string query(u"clan clash");
std::u16string text(u"Clash of Clan");
EXPECT_NEAR(FuzzyTokenizedStringMatch::PrefixMatcher(TokenizedString(query),
TokenizedString(text)),
0.98, 0.01);
}
{
std::u16string query(u"clashofclan");
std::u16string text(u"Clash of Clan");
EXPECT_NEAR(FuzzyTokenizedStringMatch::PrefixMatcher(TokenizedString(query),
TokenizedString(text)),
1.0, 0.01);
}
{
std::u16string query(u"coc");
std::u16string text(u"Clash of Clan");
EXPECT_EQ(FuzzyTokenizedStringMatch::PrefixMatcher(TokenizedString(query),
TokenizedString(text)),
0.0);
}
{
std::u16string query(u"c o c");
std::u16string text(u"Clash of Clan");
EXPECT_EQ(FuzzyTokenizedStringMatch::PrefixMatcher(TokenizedString(query),
TokenizedString(text)),
0.0);
}
{
std::u16string query(u"wifi");
std::u16string text(u"wi-fi");
EXPECT_NEAR(FuzzyTokenizedStringMatch::PrefixMatcher(TokenizedString(query),
TokenizedString(text)),
0.94, 0.01);
}
{
std::u16string query(u"clam");
std::u16string text(u"Clash of Clan");
EXPECT_EQ(FuzzyTokenizedStringMatch::PrefixMatcher(TokenizedString(query),
TokenizedString(text)),
0.0);
}
{
std::u16string query(u"rp");
std::u16string text(u"Remove Google Play Store");
EXPECT_EQ(FuzzyTokenizedStringMatch::PrefixMatcher(TokenizedString(query),
TokenizedString(text)),
0.0);
}
{
std::u16string query(u"remove play");
std::u16string text(u"Remove Google Play Store");
EXPECT_NEAR(FuzzyTokenizedStringMatch::PrefixMatcher(TokenizedString(query),
TokenizedString(text)),
1.0, 0.01);
}
{
std::u16string query(u"google play");
std::u16string text(u"Remove Google Play Store");
EXPECT_NEAR(FuzzyTokenizedStringMatch::PrefixMatcher(TokenizedString(query),
TokenizedString(text)),
0.99, 0.01);
}
}
TEST_F(FuzzyTokenizedStringMatchTest, AcronymMatchTest) {
{
std::u16string query(u"coc");
std::u16string text(u"Clash of Clan");
EXPECT_NEAR(FuzzyTokenizedStringMatch::AcronymMatcher(
TokenizedString(query), TokenizedString(text)),
0.84, 0.01);
}
// TODO(crbug.com/1336160): Consider allowing acronym matching for query with
// space in between.
// E.g., query: "c o c" and text: "Clash of Clan".
// But we may also want to exclude some cases.
// E.g., query: "c oc" and text: "Clash of Clan".
{
std::u16string query(u"c o c");
std::u16string text(u"Clash of Clan");
EXPECT_EQ(FuzzyTokenizedStringMatch::AcronymMatcher(TokenizedString(query),
TokenizedString(text)),
0.0);
}
{
std::u16string query(u"cloc");
std::u16string text(u"Clash of Clan");
EXPECT_EQ(FuzzyTokenizedStringMatch::AcronymMatcher(TokenizedString(query),
TokenizedString(text)),
0.0);
}
}
TEST_F(FuzzyTokenizedStringMatchTest, ParamThresholdTest) {
FuzzyTokenizedStringMatch match;
{
std::u16string query(u"anonymous");
std::u16string text(u"famous");
EXPECT_LT(
match.Relevance(TokenizedString(query), TokenizedString(text), true),
0.64);
}
{
std::u16string query(u"CC");
std::u16string text(u"Clash Of Clan");
EXPECT_LT(
match.Relevance(TokenizedString(query), TokenizedString(text), true),
0.5);
}
{
std::u16string query(u"Clash.of.clan");
std::u16string text(u"ClashOfTitan");
EXPECT_LT(
match.Relevance(TokenizedString(query), TokenizedString(text), true),
0.77);
}
}
TEST_F(FuzzyTokenizedStringMatchTest, ExactTextMatchTest) {
FuzzyTokenizedStringMatch match;
std::u16string query(u"yat");
std::u16string text(u"YaT");
const double relevance =
match.Relevance(TokenizedString(query), TokenizedString(text), false);
EXPECT_GT(relevance, 0.35);
EXPECT_DOUBLE_EQ(relevance, 1.0);
EXPECT_EQ(match.hits().size(), 1u);
EXPECT_EQ(match.hits()[0].start(), 0u);
EXPECT_EQ(match.hits()[0].end(), 3u);
}
TEST_F(FuzzyTokenizedStringMatchTest, DiacriticsStripTest) {
FuzzyTokenizedStringMatch match;
std::u16string text = u"áêïôu";
std::vector<std::u16string> queries = {u"aeiou", u"ÀēíÔù", u"aÉiøÚ",
u"ÅĒÎÓÙ"};
std::vector<double> scores;
for (const auto& query : queries) {
const double relevance =
match.Relevance(TokenizedString(query), TokenizedString(text),
kUseWeightedRatio, /*strip_diacritics*/ true);
scores.push_back(relevance);
VLOG(1) << FormatRelevanceResult(query, text, relevance,
/*query_first*/ false);
}
ExpectAllNearlyEqual(scores);
}
} // namespace ash::string_matching
Codebase Browser
chromium