短语相似性计算算法及其在“自动完成”功能中的应用。

• 下载演示 - 31.3 KB 

引言

本文描述了一种用于在GUI的文本框中构建“自动完成列表”的算法。 

本文附带的演示应用程序实现了该算法。演示程序使用C#作为Silverlight应用程序实现。Silverlight应用程序已部署在http://files.rsdn.ru/44022/AutocompleteTextBox.html；您无需下载和编译附带的源代码即可立即尝试。

目标读者

本文的潜在读者是希望在其应用程序中实现“智能”自动完成算法的开发人员。“智能”在此处的意思如下：一种计算匹配的“自动建议字符串”的“相关性排名”并按“排名”降序排列结果的算法。

免责声明和限制

随附的演示并非“即插即用”的“控件”，您可以将其“拖放”到应用程序中。它更多的是关于如何实现文章中描述的算法的一个示例。

随附的演示是一个Silverlight应用程序；但是，当然，这种方法几乎可以用于任何类型的GUI应用程序——在网页上（使用JavaScript）、在桌面应用程序中等等。

演示中的算法实现包含几个仅适用于英语的“硬编码”事实（例如“the”之类的“第二类词”列表）。因此，演示程序只能用于英语查询。如果您想为其他语言使用该算法，请将您语言特有的“第二类词”列表填充进去。

背景

“自动完成”的概念可以定义为“当用户在文本控件中键入文本时，提供一个‘自动完成列表’”。到目前为止，这种技术已成为事实上的标准。下面是具有此功能的几款知名应用程序的屏幕截图。

 

等等，等等。

例如，微软在其“设计优秀的Windows生产力应用程序”文章（http://msdn.microsoft.com/en-us/library/windows/apps/hh868273.aspx）中推荐使用自动完成功能。

自动完成功能已添加到各种工具包中的各种GUI控件中。例如，.NET Silverlight有一个名为AutoCompleteBox的控件（http://msdn.microsoft.com/en-us/library/system.windows.controls.autocompletebox(v=vs.95).aspx)。 .NET WPF工具包也包含自己的AutoCompleteBox（http://iserialized.com/using-the-autocompletebox-in-the-wpf-toolkit/）。这些都是不错的控件；但是它们的“匹配过滤器”非常简单。即，用于将输入文本与“可能值数组”进行“匹配”并生成“自动完成列表”的过滤器。这些过滤器提供了以下“匹配规则”：包含、以...开头、相等（区分大小写或不区分大小写）；仅此而已。当然，这些过滤器不会尝试按“相关性降序”对匹配值进行排序。

这就是为什么我尝试实现一个比典型“自动完成控件”中使用的算法“更智能”的算法。

算法的输入、输出和使用场景

算法假设有一个带有文本字段（“文本框”等）的应用程序。该字段有一个用于自动完成功能的“可能值”列表。

随附的演示是此类应用程序的一个示例。它向电影数据库发出搜索查询。

当然，查询的性质对于算法来说并不重要。

当应用程序的用户在此字段中开始键入文本时，算法会将输入的文本（我们称之为查询）与可能值进行匹配。算法返回一个“匹配”的可能值列表。列表按“相关性”降序排序。“相关性”在此处是指可能值与给定查询之间的相关程度。

应用程序应将返回的列表显示为给定查询的“自动完成列表”。

算法的主要思想

“相似度因子”

算法的核心思想是使用我们称之为“相似度因子”。

换句话说，算法考虑以下问题：“给定的可能值和查询彼此之间‘有多相似’？”算法计算一个名为SimilarityRank的数字，该数字表示它们之间的“相似度”。算法的输出列表按SimilarityRank降序排列。因此，为（PossibleValue, Query）对计算出的SimilarityRank值代表了PossibleValue与Query的“相关性”。

当然，与给定查询“完全不相似”的可能值不会包含在输出列表中。

示例

在上图所示，算法已将几个可能值与输入的查询“st”进行了“匹配”。值“Streets”具有最高的SimilarityRank，排在输出列表的第1位。值“Streets of Fire”具有较低的SimilarityRank，排在输出列表的第2位，以此类推。

SimilarityRank如何计算

用于计算SimilarityRank的主要思想如下：

1. 字符串比较（用于“匹配”）不区分大小写。
2. 将可能值与查询进行“匹配”是“逐词”操作。换句话说，可能值和查询都将“分割”成单词。

   我们假设，当查询的所有单词都在可能值中按相同顺序找到时，一个可能值就“匹配”了该查询。

   “在可能值中找到”表示：查询的单词应等于可能值的单词；或者成为可能值的单词的前缀。

   示例：假设我们有一个查询“leading spaces”，那么“the leading and trailing Spaces”这个可能值就匹配该查询。但是，“spaces that are leading or trailing”这个可能值不匹配“leading spaces”——查询中的两个单词都在可能值中找到；但顺序不正确。

   另一个示例：假设我们有一个查询“lead space”。那么“the leading and trailing spaces”这个可能值就匹配该查询。但是，“cheerleaders and spaces”这个可能值不匹配该查询——单词“lead”在单词“cheerleaders”中找到，但不是开头的，所以它不是单词“cheerleaders”的“前缀”。

   “未匹配”的可能值不会包含在算法的输出列表中。

3. 对于查询单词与其“匹配”的可能值单词的每一对，我们使用以下规则：它们长度越接近，单词就越“相似”。

   示例：假设我们有一个可能值单词“relativeness”和一个查询单词“rel”。它们匹配，这没问题。但是，“相似度”不高：单词“rel”的长度仅为“relativeness”长度的25%。

   现在，假设查询单词是“relative”而不是“rel”。“relative”和“relativeness”之间的“相似度”比“rel”和“relativeness”之间的“相似度”高得多。“relative”的长度占“relativeness”长度的66%。

   我们将此称为“单词长度因子”。

4. 如果满足以下情况，我们将为查询单词与其“匹配”的可能值单词的每一对增加SimilarityRank：
   • 查询单词包含大写字母；

     和

   • 查询单词在可能值中的出现精确（区分大小写）等于该查询单词；

   示例：假设我们有一个查询“Main”和两个可能值：“Maine”和“maine”。

   它们都匹配查询；但是“Maine”的SimilarityRank更高。原因是：查询“Main”包含大写字母。并且“Main”在“Maine”中的出现（作为查询的子串）在区分大小写的情况下与查询精确相等；而第二个可能值中的子串“main”则不是。

   我们将此称为“大写字母因子”。

5. 对于查询单词与其“匹配”的可能值单词的每一对，SimilarityRank取决于可能值单词所属的“单词类别”。

   如果可能值单词属于“1^st类”，则SimilarityRank较高。如果可能值单词属于“2^nd类”，则SimilarityRank较低。

   单词的“类别”由以下规则定义（仅限英语；其他语言可能需要其他规则）：“第二类”由冠词、介词等单词组成。这些单词比其他单词“不重要”。在某些搜索引擎中，它们被称为“停用词”并完全被忽略。我们的算法不会完全忽略它们；但认为它们是“不太重要的”。而“第一类”是除“第二类”之外的所有其他单词。

   在当前的算法实现中，以下单词属于“第二类”：“the”、“a”、“at”、“in”、“on”、“of”、“off”、“into”、“onto”、“by”。

   当然，这个列表可以扩展。

   我们将此称为“单词类别因子”。

6. “匹配”的可能值单词在短语开头的位置越接近，SimilarityRank越高。

   示例：假设我们有一个查询“green”和2个可能值：“green light”和“light green”。它们都匹配查询；但是“green light”的SimilarityRank更高。原因是：“green”这个单词在“green light”中位于第1位，而在“light green”中仅位于第2位。

   我们将此称为“单词位置因子”。

7. 查询的长度与“匹配”的可能值的长度越接近，SimilarityRank越高。

   我们将此称为“短语长度因子”。

   示例：假设我们有一个查询“green”和2个可能值：“green light”和“green light in the window tonight”。它们都匹配查询；但是“green light”的SimilarityRank更高。原因是：查询“green”的长度约占“green light”长度的50%；而仅占“green light in the window tonight”长度的约15%。

算法细节

在上一节中，我描述了算法的主要思想。在本节中，我将提供完整描述——如何为（Query, PossibleValue）对计算数值SimilarityRank。

我建议您在阅读以下描述时查看随附的源代码。

1. 使用以下分隔符将查询和可能值分别拆分为单词：{空格}、{制表符}、!、.、{逗号}、;、（）、\、/、+、-、:、“”、“[”、“]”、“?”、{ }、|、{长破折号}、{短破折号}。

2. 查找查询在可能值中的所有出现。当满足以下条件时，会发生“出现”：
   • 查询的每个单词等于可能值的单词；或者成为可能值单词的前缀；

     和

   • 匹配的可能值单词的顺序与其对应的查询单词的顺序相同。

   单词的比较是不区分大小写的。

   示例：假设我们有PossibleValue“Aa b c a bb”和Query“a b”。PossibleValue有两个“a b”的“出现”：“Aa b c a bb”和“Aa b c a bb”。

   示例：假设我们有PossibleValue =“a b”和Query =“b a”。PossibleValue没有“b a”的“出现”。事实上，PossibleValue包含“a”和“b”这两个单词，但顺序与查询中的顺序不符。

3. 如果可能值没有查询的出现，则SimilarityRank为0。退出算法。

4. 为给定的（Query, PossibleValue）对计算一个名为PhraseLengthFactor的值。有关计算细节，请参见下文。

5. 以如下方式为每个出现计算一个名为SimilarityRankOfTheOccurence的值：

   5.1. 为（<查询单词>，<匹配查询单词的<可能值单词>）的每一对计算一个名为WordsSimilarityRank的值。它显示了单词之间的“相似度”。

   示例：假设我们有PossibleValue“aa bbb c d”和Query =“a b”。然后我们为（“a”、“aa”）这对计算WordsSimilarityRank值；以及为（“b”、“bbb”）这对计算另一个WordsSimilarityRank值；

   有关计算细节，请参见下文。

   5.2. 为（<查询单词>，<匹配查询单词的<可能值单词>）的每一对计算一个名为WordPositionFactor的值。

   示例：假设我们有PossibleValue =“aa bbb c d”和Query =“a b”。然后我们为（“a”、“aa”）这对计算WordPositionFactor值；以及为（“b”、“bbb”）这对计算另一个WordPositionFactor值。

   有关计算细节，请参见下文。

   5.3. 按照以下方式计算给定出现的SimilarityRankOfTheOccurence：

   SimilarityRankOfTheOccurence = WordsSimilarityRank * WordPositionFactor * PhraseLengthFactor 

6. 现在我们已经为给定的（Query, PossibleValue）对中的每个“出现”计算出了SimilarityRankOfTheOccurence值。找出所有SimilarityRankOfTheOccurence值中的最大值。这将是（Query, PossibleValue）对的SimilarityRank。

PhraseLengthFactor如何计算

在这里的输入是一个（Query, PossibleValue）对。它们已经“分割”成单独的单词；可以表示为单词数组。

我们按照以下方式计算PhraseLengthFactor（代码如下为C#）：

double AddendForWordWeightCalculation = 10.0;
double MaxQueryRelativeWeight = 1.0; 
double MinQueryRelativeWeight = 0.5; //Should be in]0, MaxQueryRelativeWeight[ range

double weightOfQuery = 0.0;
for (int i = 0; i < Query.Words.Length; ++i)
{
	weightOfQuery += Query.Words[i].Length + AddendForWordWeightCalculation;
}

double weightOfPossibleValue = 0.0;
for (int i = 0; i < PossibleValue.Words.Length; ++i)
{
	weightOfPossibleValue += PossibleValue.Words[i].Length + AddendForWordWeightCalculation;
}

double prevVal = weightOfQuery / weightOfPossibleValue;

double phraseLengthFactor = MinQueryRelativeWeight + prevVal * (MaxQueryRelativeWeight - MinQueryRelativeWeight);

在给定的算法实现中，最终的PhraseLengthFactor将在[0.5, 1.0]范围内。您可以更改范围，以增加或减少PhraseLengthFactor对最终SimilarityRank的影响。例如，如果您使用MaxQueryRelativeWeight = 2.0而不是当前的1.0，PhraseLengthFactor的影响将会更大。

WordsSimilarityRank如何计算

在这里的输入是一对单词（WordOfPossibleValue, WordOfQuery）。WordOfQuery是给定查询的一个单词；WordOfPossibleValue是给定可能值的一个单词；并且该单词“匹配”WordOfQuery。例如：WordOfQuery是“th”，而“匹配”的WordOfPossibleValue单词是“That”。正如我们上面所说，WordOfQuery必须等于WordOfPossibleValue或成为其前缀才能“匹配”它。这里的比较是不区分大小写的。

我们按照以下方式计算WordsSimilarityRank：

定义一个常量IncreasingForUppercases = 1.1 

定义一个常量DecreasingFor2ndClassWord = 0.2

1. WordsSimilarityRank = WordOfQuery.Length / PossibleValue.Length
2. 如果 WordOfQuery 包含大写字母

   AND 

   WordOfQuery 等于 WordOfPossibleValue 或（区分大小写地）是其前缀

   那么

   WordsSimilarityRank = WordsSimilarityRank * IncreasingForUppercases
3. 如果 WordOfPossibleValue 属于“第二类”（有关“单词类别”的更多信息，请参见上文）

   那么

   WordsSimilarityRank = WordsSimilarityRank * DecreasingFor2ndClassWord

    

注意：

“WordsSimilarityRank = WordOfQuery.Length / PossibleValue.Length”公式实现了我们上面称之为“单词长度因子”的内容。

这里的IncreasingForUppercases实现了我们上面称之为“大写字母因子”的内容。

这里的DecreasingFor2ndClassWord实现了我们上面称之为“单词类别因子”的内容。

WordPositionFactor如何计算

在这里的输入是一个整数值PositionInPossibleValue。这是查询单词在“匹配”的可能值中的（基于零的）单词位置。例如，我们有一个查询“th”和一个可能值“Color of the night”。单词“th”在可能值的第2个单词（使用基于零的编号）中找到；因此，对于查询的给定出现，PositionInPossibleValue为2。

我们按照以下方式计算WordsSimilarityRank：

定义一个常量WordPositionFactorBonusFor1stWord = 2.0

定义一个常量WordPositionFactorAddendForCalculation = 10.0

定义一个常量WordPositionFactorMinValue = 0.3；

1. WordPositionFactor = WordPositionFactorAddendForCalculation / (WordPositionFactorAddendForCalculation + positionInPossibleValue)

2. 如果 positionInPossibleValue 为0

   那么  

   WordPositionFactor = WordPositionFactor * WordPositionFactorBonusFor1stWord
3. 如果 WordPositionFactor < WordPositionFactorMinValue

   那么

   WordPositionFactor = WordPositionFactorMinValue

注意：WordPositionFactorBonusFor1stWord在查询单词位于可能值开头时起“奖励”作用。当然，WordPositionFactorBonusFor1stWord的值必须大于1.0。

在给定实现中使用WordPositionFactorBonusFor1stWord = 2.0这个值并不是一个不能更改的“魔术数字”。例如，如果您希望“可能值开头单词的奖励”更重要，可以增加它。

WordPositionFactorMinValue必须是一个小于1.0的正数。

实现

随附的演示是一个简单的C#算法实现。类AutocompletionEngine.TextSearcher.Processor包含了算法的所有逻辑。创建一个该类的对象，使用AddPossibleValue方法用可能值填充它，然后调用Search方法，并将查询作为参数。该方法返回算法的“结果列表”——一个按SimilarityRank降序排列的“匹配”可能值列表。

静态列表AutocompletionEngine.TextSearcher.Word.ArticlesEtc包含硬编码的“第二类”单词列表。如果您希望算法能正确处理非英语查询，请用您语言的“第二类单词”填充该列表。

项目UnitTest包含一组基于NUnit的AutocompletionEngine.TextSearcher.Processor类的自动化测试。这就是为什么该项目需要nunit.framework.dll库。