将先前手写实例用于手写美化和其他应用

摘要

描述了参考先前手写实例来处理用户的当前手写实例的笔划处理系统(SPS)。在一个应用中，SPS使用户输入的新记号(对应于笔划样本序列)与同该新记号相似的各先前记号匹配。SPS随后将新记号与先前记号一起求平均来细化该新记号。这改善了新记号的外观。在另一应用中，SPS使用先前记号来产生搜索结果。在另一应用中，SPS使用先前记号来执行自动完成操作。

说明书

背景

用户可使用指示笔来在触敏显示器表面上或在数字化输入板上进行书写。这种输入模式给予用户产生任何形式的手写内容(诸如字母数字字符、图片等)的自由。然而，用户可写得很快且很粗心，由此产生不规范的字符和图片。结果，用户稍后可能难以解释他或她的书写。替换地或另选地，用户可出于审美的理由而不满意他或她的书写。

存在用于自动美化手写内容的技术。这些技术中的许多通过尝试将用户的手写与规范字符或形状匹配并随后用这些字符或形状来代替用户的手写来起作用。例如，一个这样的技术可使用手写识别来解释用户已经写好的字符和单词，并且随后用其键入的正式对应物来代替那些字符和单词。尽管有用，但这些技术具有各种缺点。例如，这些技术仅能够识别某些手写内容，而不能识别具有任何任意形式的内容。此外，这些技术仅可识别与其预期的规范对应物足够相似的字符和形状。

概述

本文中描述了基于手写内容的先前实例来处理该手写内容的笔划处理系统(SPS)。例如，在一个方法中，SPS通过接收如用户写在输入设备的书写表面上的输入笔划来起作用。SPS基于这些输入笔划样本来制定一连串记号。每一新记号对应于一系列笔划样本。对于每一新记号，SPS随后检查先前记号的集合以确定是否存在与该新记号相似的至少一个先前记号。如果是这样的，则SPS基于(诸)先前记号来执行动作。

在一个动作中，SPS基于(诸)先前记号来修改新记号以由此改善新记号的外观。例如，SPS可将新记号中的笔划样本与(诸)先前记号中的相关记号样本一起求平均。通过这么做，SPS将这些先前记号看作属于用户想要画出的新记号的形状的证据。

在另一动作中，SPS基于(诸)先前记号来提供搜索结果。例如，SPS可在包含手写的文档中标识(诸)先前记号的出现。

在另一动作中，SPS基于(诸)先前记号来执行自动完成操作。在此，SPS预测可能被确定为跟随该新记号的记号，并向用户通知该预测的记号。

SPS提供各种好处。不作为限制，SPS可处理具有任何任意形式的手写，而无需使用复杂的识别算法。此外，在美化应用中，SPS可以按保留用户的手写样式的通用外观的方式来修改用户手写。

上面的方法可以显现在各种类型的系统、组件，方法、计算机可读存储介质、数据结构、制品等等中。

提供本概述以便以简化形式介绍一些概念；这些概念将在以下的详细描述中进一步描述。本概述并不旨在标识所要求保护主题的关键特征或必要特征，也不旨在用于限制所要求保护主题的范围。

附图简述

图1示出对用于基于先前手写实例来处理手写的笔划处理系统(SPS)的概览。

图2是示出图1的SPS的一种操作方式的流程图。

图3-5示出图1的SPS的操作的示例。在这种情况下，SPS被应用来将输入手写变换成输出手写，其中输出手写表示输入手写的经美化的版本。

图6示出作为图1中示出的SPS的一个组件的记号形成模块的一个实现。记号对应于一系列在时间上毗邻的笔划样本，这些笔划样本组成用户的手写的一部分。

图7是示出图6的记号形成模块的一种操作方式的流程图。

图8示出了可由图7的记号形成模块执行的重采样操作的示例。

图9示出了可由图7的记号形成模块产生的两个记号描述符的示例。每一记号描述符描述一记号。

图10示出作为图1的SPS的另一组件的相似性评估模块的一个实现。

图11是描述图10的相似性评估模块的一种操作方式的流程图。

图12是描述作为图1中的SPS的另一组件的聚类模块的一种操作方式的流程图。

图13是可由图10的相似性评估模块执行的时间粗略级相似性处理的示例。

图14是可由图10的相似性评估模块执行的空间精细级相似性处理的示例。

图15示出两个记号的示例，其中一个记号紧接着另一个记号出现。

图16是描述标识各相似记号聚类之间的关系的一种方式的流程图。

图17是描述(例如通过使用图16的过程产生的关系)加速由图10的相似性评估模块执行的相似性处理的一种方式的流程图。

图18示出作为图1的SPS的另一组件的记号细化模块的一个说明性实现。

图19是示出图18的记号细化模块的一种操作方式的流程图。

图20是可由图18的记号细化模块执行的对齐处理的一示例。

图21示出搜索功能的一个实现。该搜索功能利用图10的相似性评估模块的结果。

图22示出自动完成功能的一个实现。该自动完成功能也使用图10的相似性评估模块的结果。

图23是示出(图21的)搜索功能和(图22的)自动完成功能的一种操作模式的流程图。

图24示出图1的SPS的独立实现。

图25示出图1的SPS的分布式实现。

图26示出可以被用来实现前面的附图中所示出的特征的任何方面的说明性计算功能。

贯穿本公开和各附图，相同的编号参考相同的组件和特征。100系列标号指的是最初在图1中所找到的特征，200系列的标号指的是最初在图2中找到的特征，300系列的标号指的是最初在图3中找到的特征，依此类推。

详细描述

本发明是按如下方式来组织的。章节A呈现基于先前记号来处理当前记号(表示手写)的笔划处理系统(SPS)的概览。SPS包括记号形成模块、相似性评估模块、记号细化模块和可任选的其他应用模块。章节B提供关于记号形成模块的进一步细节。章节C提供关于相似性评估模块的进一步细节。章节D提供关于记号细化模块的进一步细节。章节E提供关于诸如搜索功能和自动完成功能之类的其他应用模块的进一步细节。并且，章节F描述可以被用来实现前述各节所描述的特征的任何方面的说明性计算功能。

作为预备，一些附图在被不同地称为功能、模块、特征、元素等的一个或多个结构组件的上下文中描述概念。附图中示出的各组件可以由任何物理和有形的机制(例如，由正在计算机装备上运行的软件、硬件(例如芯片实现的逻辑功能)等和/或以上的任意组合)以各种方式来实现。在一种情况下，附图中所示出的将各种组件分离为不同的单元可以反映在实际实现中使用对应的不同的物理和有形的组件。另选地或者另外地，附图中所示出的任何单个组件都可以通过多个实际物理组件来实现。另选地或另外地，附图中的任何两个或更多分开组件的描绘可以反映单个实际物理组件所执行的不同功能。图26(将依次讨论)提供关于附图中所示的功能的一个说明性物理实现的附加细节。

其他附图以流程图形式描述了概念。以此形式，某些操作被描述为构成以某一顺序执行的不同的框。这些实现是说明性而非限制性的。此处描述的某些框可被分组在一起并在单个操作中执行，某些框可被分成多个组件框，并且某些框可以按与此处所示出的不同的次序来执行(包括以并行方式执行这些框)。流程图中示出的框可以任何方式由任何物理和有形机制来实现，例如由正在计算机装备上运行的软件、硬件(如芯片实现的逻辑功能)等和/或它们的任何组合来实现。

至于术语，短语“被配置成”包含任何类型的物理和有形的功能可以被构建来执行已标识的操作的任何方式。功能可以被配置成使用例如正在计算机装备上运行的软件、硬件(例如，芯片实现的逻辑功能)等和/或其任何组合来执行操作。

术语“逻辑”包含用于执行任务的任何物理和有形的功能。例如，流程图中示出的每一个操作都对应于用于执行该操作的逻辑组件。操作可以使用例如正在计算机装备上运行的软件、硬件(例如，芯片实现的逻辑功能)等和/或其任何组合来执行操作。在由计算装备实现时，逻辑组件表示作为计算系统的物理部分的、无论如何实现的电子组件。

权利要求中的短语“用于…的装置”(如果被使用)旨在援引35U.S.C.§112第六段的规定。除了本特定短语之外，没有其他语言旨在援引该法条的该部分的规定。

下列的阐述可以将一个或多个特征标识为“可任选的”。这种类型的陈述不应该被解读为可以被视为可选的特征的穷尽的指示；也就是说，其他特征也可以被视为可选，虽然在文本中没有明确地标识。最后，术语“示例性”或“说明性”指的是可能多个实现中的一个实现。

A.概览

图1示出用于处理手写的说明性笔划处理系统(SPS)102。从高级观点来看，SPS102尝试找到匹配当前手写实例的先前手写实例。SPS随后基于先前手写实例执行一个或多个动作。在一个应用中，SPS基于先前手写实例修改当前手写实例，从而使得该当前实例更紧密地类似于先前手写实例。

用户可使用输入设备104来输入手写。SPS102处理该手写并产生输出信息，该SPS将该输出信息呈现在输出设备上。在一些情况下，输入设备104与输出设备是相同的机制。例如，输入设备104可对应于具有触敏显示表面的任何类型的计算机设备。例如，计算机设备可对应于个人计算机、膝上型计算机、平板型计算机、智能电话等等。用户可使用指示笔、手指或其他书写实现在触敏显示表面上创建标记。在这些情况下，SPS102还可将输出信息呈现在同一触敏显示表面上。例如，SPS102可将输入手写的经美化版本呈现在用于录入输入手写的同一触敏显示表面上。

在另一方面，输入设备104和输出设备可对应于分开的机制。例如，输入设备104可对应于数字化垫(也被称为图形板)。输出设备可对应于与数字化垫分开的显示设备。用户可使用任何书写实现来在数字化垫上作出标记，同时观察显示设备上呈现的所得的手写。

SPS102本身可按任何方式实现。例如，SPS102可对应于输入设备104内的使用软件、硬件等或其任何组合来实现的模块。在另一情况下，SPS102可由与输入设备104分开的计算机设备来实现。章节F提供关于SPS102的各种物理实现的进一步细节。

SPS102包括(或可被概念化成包括)执行不同功能的不同子模块。例如，记号形成模块(TFM)106接收组成用户产生的手写的输入笔划样本。TFM106可随后可任选地重采样输入笔划样本以产生经重采样的笔划样本。随后，TFM106可随着用户产生手写，基于经重采样的笔划样本定义一连串的记号。记号对应于一系列n个的连续(时间上毗邻的)笔划样本。不作为限制，例如，记号可对应于31个共同地描述几个手写字符的经重采样笔划样本。如本文中使用的术语“新的记号”指代由TFM106定义的最新近记号。章节B提供关于TFM106的操作的进一步说明性细节。

数据存储108存储多个先前记号。每一先前记号对应于(与作为由TFM106定义的最新近记号的新记号有关的)由TFM106先前定义的记号。如以下将更详细阐述的，数据存储108可将这些先前记号作为多个聚类来维护。每一聚类包括一组相似的先前记号。当两个记号拥有相似笔划样本并由此在整体上很可能属于同一语义内容(例如，同一字符、图片等)时，这两个记号是相似的。每一聚类与聚类表示(诸如，聚类均值)相关联。如以下将描述的，聚类的聚类均值对应于表示该聚类中的各记号的平均的记号。

相似性评估模块(SAM)110检查数据存储108中的先前记号以确定是否存在与新记号相似的先前记号。在一个实现中，SAM110可通过确定是否存在与新记号相似的任何聚类表示(例如，聚类均值)来执行该任务。

虽然图1中未示出，但SPS102还可包括聚类管理模块。聚类管理模块将新记号添加到与该新记号最相似的聚类中。如果不存在与新记号合适地相似的聚类，则聚类管理模块可创建新聚类。该新聚类最初将仅包含对应于该新记号的一个成员。章节C提供关于SAM110和聚类管理模块的操作的进一步说明性细节。

记号细化模块(TRM)112基于已被SAM110标识出的相似的先前记号(如果有的话)来修改新记号的外观。TRM112可通过首先将(诸)先前记号中的样本与新记号中的样本对齐来执行该任务。这会产生相关的样本。TRM112可随后对相关的样本一起求平均。较不正式地说，TRM112产生作为原始的新记号和(诸)先前记号的混合的经修改的新记号。因此，TRM112将先前的相似记号隐式地看作用户想要创建的与新记号有关的字符和/或形状的证据。章节D提供关于TRM112的操作的进一步说明性细节。

图1还指示取代TRM112或作为其补充，SPS102还可提供可任选的其他应用114。例如并非作为限制，SPS102可包括搜索功能和自动完成功能。章节E提供关于这两个应用的进一步说明性细节。

图2示出提供图1的SPS102的一种操作方式的概览的过程202。在框204，SPS102接收输入笔划样本。在框206，SPS102(可任选地在执行重采样操作之后)基于输入笔划样本形成新记号。在框208，SPS102检查先前令牌的集合以确定与新令牌相似的至少一个先前令牌(如果存在的话)。在框210，SPS102基于框208的结果执行一个或多个动作。例如，SPS102可执行基于先前记号来美化新记号的记号细化操作。或者SPS102可执行搜索操作、自动完成操作等。在框212，SPS102提供传达在框210执行的处理的结果的输出信息。

图3-5提供使用SPS102来美化手写的示例。每一附图包括两列。第一列(被标记为“细化前”)包括在应用细化之前由用户创建的一系列原始手写实例。第二列(被标记为“细化后”)包括由SPS102产生的一系列经美化的手写实例。即，第二列中的每一经美化的手写实例均是第一列中的毗邻的原始手写实例的经美化的对应物。

首先考虑图3的情况。此处，细化前列包括由用户按从上到下的次序产生的同一短语“Pencil+Paper(笔+纸)”的一系列实例。即，最上面的“Pencil+Paper”的实例表示由用户产生的该短语的第一个实例，而最下面的“Pencil+Paper”的实例表示由用户产生的该短语的最后一个实例。细化后列示出了在应用了细化后由SPS102产生的一系列对应短语。

注意，当用户重复短语“Pencil+Paper”时，SPS102累积该SPS可从其评估用户书写该短语的典型方式的知识库。SPS102可通过校正由用户产生的短语“Pencil+Paper”的新实例的外观从而使得这些新实例更接近地符合该短语的先前实例来利用该知识。例如，注意原始短语的第四实例具有(相对于先前实例评估的)两个异常(302、304)对于异常302，“Pencil”的字符“P”的曲线段具有越过字符“P”的垂直直线段的尾部。对于异常304，“Paper”中的“P”的直线段向外扩展而形成了环。SPS102基于“Paper+Pencil”的不包含这些异常的先前实例产生校正302’和304’。例如，在校正302’中，SPS102移除越过直线段的尾部。在校正304’中，SPS102压缩与异常304相关联的环。

SPS102可按任何方式来显示与原始实例有关的经美化实例。在一种情况下，一旦计算出原始实例的经美化对应物，SPS102就可用其经美化对应物来盖写原始实例。例如，一旦计算出短语“Pencil+Paper”的经美化对应物，SPS102就可用这些短语的经美化对应物来替换该短语的原始实例。SPS102还可使用各种时间混合策略来实现该效果，诸如通过在用户书写时将原始实例逐渐地变形为经美化实例来实现该效果。用户可将该效果作为跟踪他或她的手写的细化窗口来感知，在该细化窗口中，用户的原始手写被逐渐地变形为经美化手写。

SPS102还可调整经美化实例的位置以使得这些经美化实例与之前的书写对齐，以由此防止经美化书写偏离之前的书写。SPS102可通过计算原始实例的平均位置以及经美化实例的平均位置来执行该任务。SPS102可随后使经美化实例移位这两个平均数之差。

在另一实现中，SPS102可诸如通过以下方式来将经美化实例写在输出设备上而无需移除原始实例：将经美化实例显示在原始实例下方、或将经美化实例显示在原始实例右边(如图3所示)、或将经美化实例显示在原始实例左边、或将经美化实例显示在可选的弹出窗口中、或按相对于原始实例的任何其他关系来显示经美化实例。还有一些其它呈现策略也是可能的。SPS102还可给予用户“撤消”选项，该选项允许用户移除美化效果。

还应注意的，在以上示例中，SPS102基于更具涵盖性的过去手写语料库来对紧接在前的新手写的移动窗口进行操作。SPS102不用于校正在该窗口之前发生的过去手写的实例。这意味着，在该窗口继续移动后，出现在该窗口“后面”的手写变成固定的(指它不再经受优化)。但也有可能修改在该窗口后面的手写。例如，在另一实现中，用户可指令SPS102对文档中的手写作出全局校正，该全局校正已基于在该文档和任何其他地方中表达的先前手写的完整语料库产生。

图4示出SPS102细化原始手写实例以产生经美化手写实例的另一示例。此处，用户连写出单词“stylus(指示笔)”，如细化前列中所指示的(其中仅最后四个条目被示出)。SPS102将单词“stylus”的这些原始实例修改成经美化实例，如细化后列中所指示的(其中再次仅最后四个条目被示出)。例如，考虑单词“stylus”的原始实例中的异常402对应于其中用户将字母“y”的扩张段产生为单根线的情况。假设只要用户通常将该段写成为环而非写成为单根线条，这就是异常；然而，应注意，这在图4所示的有限数目的样本中并不明显。响应于这一发现，SPS102可用其校正402'来替换异常402。

图3和4对应于其中手写对应于字母数字字符的情况。但是，更一般地，SPS102按不可知用户的手写的性质的方式来执行分析。换言之，SPS102可美化类似于先前输入标记的任何标记。那些标记可对应于任何语言中的重复符号、重复图片或不具有任何含义的重复构造。

例如，图5示出了其中用户产生车辆的一系列粗糙图片的示例，如细化前列中所示出的。一旦SPS102累积了与该图片相关联的先前记号，SPS102就可产生图片的经美化对应实例，如细化后列中所示出的。例如，注意一个这样的原始实例包括其中轮胎与车辆的主体重叠达与车辆的先前图片相比更大的程度的异常502。SPS102产生降低该异常的程度的校正502’。注意，SPS102没有完全地校正该异常，因为轮胎仍与车辆的主体重叠达某一程度。这是因为原始图片中的异常502足够大，使得无法依据该图片的先前实例来将其完全“校正”。这进而源于经美化的绘图表示图片的原始实例(其包含异常)和图片的先前实例(其忽略异常达到可变程度)的平均的事实。

作为总体特征，注意SPS102通过基于用户的手写的先前实例来校正同一用户的手写来起作用。由此，SPS102作出的校正一般符合用户的书写样式而非某一规范模板，该规范模板定义什么构成字符或地理形状的“正确”形式。例如，如果用户重复地按特异方式形成某字符，则SPS不会将该字符认为有异常，并且由此将不会纠正它。在一个实现中，数据存储108可存储跨越对应于任何时间长度(例如，天、月、年等)的任何数目的先前会话的过程以及由用户产生的任何数目文档的用户的先前记号。可任选地，SPS102还可基于每一记号的创建时间对每一记号进行加权，从而将更多的权重赋予更新近的记号。

在另一实现中，SPS102可依赖于包含由多个用户产生的记号的数据存储。这样的数据存储可被看作用户不可知的记号集合。在另一实现中，SPS102可依赖用户不可知的记号集合仅达该SPS102还没有累积特定用户的手写样式的足够知识的程度。例如，当个体用户先开始使用SPS102时，SPS102可几乎排他地使用用户不可知的记号集合。此后，SPS102可将其对用户不可知记号集合的依赖性降低成与用户的个人记号集合的当前大小成比例。

在另一实现中，SPS102可存储用户不可知记号集合的多个版本，每一版本对应于特定书写样式。SPS102可基于用户的书写样式来对他或她进行分类，并随后使用适合于该样式的任何用户不可知的记号集合。还有一些其它实现也是可能的。

然而，为了简化并方便解释，该描述的其余部分将假设数据存储108存储用特定用户的手写产生的先前记号的集合，以供在对那个用户的手写进行美化时使用。

B.记号形成模块

图6示出TFM106的一个实现。TFM106包括可任选的重采样模块602和记号创建模块604。记号重采样模块602接收已使用任何采样技术创建的原始笔划样本。每一原始笔划样本在本文中被表示为φ^o。记号重采样模块602随后生成手写的另一表示，从而得到重采样笔划样本。每一重采样的笔划样本在本文中被表示为φ^r。记号创建模块604基于重采样的笔划样本产生跨越该时间过程的一系列记号606。每一记号在本文中被表示为φ。

更具体地，在一种情况下，重采样模块602可产生手写的重采样版本，其中产生样本的速率直接随手写的曲率而变化。这意味着重采样模块602可用与曲线段相比更少的样本点来表示相对直的线段。

在一个实现中，每当重采样模块602提供新的笔划样本(φ^r)时，记号创建模块604都产生新的记号(φ)。例如，假设记号创建模块604将新记号定义为一连串的n个样本，即其中在一种情况下，n＝31。当记号创建模块604接收到下一笔划样本(φ^r)时，它创建具有n个样本的新记号。新的记号与紧接在前的记号相同，除了该新的记号相对于该先前记号移位了一个样本位置以外。换言之，如果n＝31，则该新的记号共享与先前记号共同的30个样本。图6图示地示出记号606的以上所述的重叠性质。

记号尺寸被选为适应于形成有意义的聚类。如果记号尺寸太大，使得该记号涵盖整个单词(例如，单词“mountain(山)”)，则SPS102将不能够快速地形成针对该记号的聚类，因为可预期用户会不频繁地写这个单词。而如果记号尺寸太小(使得该记号仅涵盖单个字符)，则该记号将不会捕捉反映它如何与其他记号组合的上下文信息。例如，用户写字符“a”的方式将取决于该字符“a”之前和之后的字符而不同。在许多实现中将记号尺寸选定为大到足以涵盖几个字符(例如，2-3个字符)会提供令人满意的解决方案。例如，尽管单词“mountain”不频繁出现，但字符组合“oun”十分经常地出现。更一般地，记号创建模块604可被配置成产生任何尺寸的记号，这取决于任何一个(或多个)环境特定因素。

图7示出了表示重采样模块602的一种操作方式的过程702。作为说明而非限制描述了过程702；其他实现可采用其他重采样策略。在这种情况下，假设原始笔划样本和重采样笔划样本两者都是用极坐标来表示的。即，每一样本由三个值(r，θ，p)来定义，其中r是指示线段的长度的幅度值，θ是指示该线段相对于某一全局参考帧的取向的角度值，并且p是指示笔(或其他书写实现)在输入设备104的表面上的压力。零压力指示指示笔不与输入设备104的书写表面接触。

作为概览，重采样模块602将原始笔划样本分配给“桶”，其中每一桶对应于特定重采样笔划样本。更具体地，重采样模块602用于将原始笔划样本添加到桶，直到与该桶相关联的基于曲率的值超过某一阈值。当这个发生时，重采样模块602将前进到桶序列中的下一桶。通过这种方式，重采样模块602将为曲线“填充”与直线相比更多的桶。

更具体地，在框704，重采样模块602接收新的原始笔划样本φ^o。在框706，重采样模块602相对于之前的原始笔划样本来确定新的原始笔划样本φ^o指示用户是否已将指示笔放置在输入设备104的书写表面上或已将该指示笔从书写表面上移除。如果如此，则在框708，重采样模块602产生新的重采样笔划样本φ^r。重采样模块602还“固定”它先前创建的先前重采样笔划样本(如果有的话)；这意味着重采样模块602将停止将原始笔划样本添加到那个先前“桶”。”

在框710，假设新的原始笔划样本对应于用户已在书写表面上产生的标记。用极坐标来表达后，假设该标记具有长度r_k、取向θ_k和压力p_k。重采样模块602基于当前原始笔划样本相对于先前原始笔划样本的取向的改变来递增变量值z_k。即，z_k是的某个函数，其中其中Δ_θ(a，b)＝min(|θ_a-θ_b|，2π-|θ_a-θ_b|)。

在框712，重采样模块602确定z_k的值是否超过某一阈值。例如，假设重采样模块602创建z_k的从0到1.0的值的桶，以及z_k的从1.0到2.0的值的桶并以此类推。在这种情况下，在框712，重采样模块712可确定z_k的值是否已移动到下一整数桶。

如果该阈值尚未被超过，则重采样模块602可将新的原始笔划样本添加到在当前“桶”中创建的现有重采样笔划样本。假设当前桶中累积的线段具有幅度值r_l、取向θ_l和压力p_l。重采样模块可将重采样笔划样本的新笛卡尔端点(x,y)更新成x＝r_kcos(θ_k)+r_lcos(θ_l)和y＝r_ksin(θ_k)+r_lsin(θ_l)。重采样模块602可将累积的重采样样本的新压力更新成p_l＝(r_k*p_k+r_l*p_l)/(r_k+r_l).重采样笔划样本的经更新幅度(在添加了新样本后的经更新幅度)对应于r_l＝||x，y||。重采样笔划样本的经更新取向对应于θ_l＝arctan(y，x)。

在框708，替换地假设将当前原始笔划样本添加到当前桶会导致z_k的值超过阈值。作为响应，重采样模块602创建新的桶(对应于新的重采样笔划样本)并将原始笔划样本作为第一条目添加到该新的桶。在这时，先前桶(对应于先前重采样笔划样本)变成固定的，并且重采样模块602将将来接收到的原始笔划样本添加到该新的桶。

任何函数都可用于计算z_k。不作为限制，在一个示例中，重采样模块602使用以下等式来计算z_k。

z_k＝z_k-1+min(1，αβ_iv_k)。

使用该等式，重采样模块602通过将1和中较小一个添加到z_k的先前值(即，z_k-1)来产生新的值z_k。值1确保重采样模块602将z_k的值增加不超过1，其防止过程702跳过桶，并且其相应地防止从具有零长度幅值的条目创建的记号。参数α控制采样的密度。不作为限制，α可被设为12/π，其将为画出的圆粗略地产生24个样本。参数β_i防止原本将因指示笔位置的离散化而引起的差错，即通过在笔划幅度r_i当前较小时减小z的值来防止该差错，其中r_i对应于r_k正被添加到的线段的长度。不作为限制，在一种情况下，重采样模块602可将参数β_i计算成

图8示出了阐明图7的过程702的操作的示例。该图示出由多个原始笔划样本组成的原始手写802。每一原始笔划样本由开始样本点和结束样本点(其中每一样本点在图7中均被表示成黑点)来划界。开始样本点与先前样本(如果有的话)的结束样本点相同。重采样模块602将原始手写802转换成重采样手写804。重采样手写804同样由多个重采样笔划样本组成，这些重采样笔划样本中的每一者由开始样本点和结束样本点来表示。

基于过程702，重采样模块602基于原始手写802中的曲率程度来执行重采样。更具体地，当值z_k超过阈值时(诸如当值z_k超过与当前桶相关联的整数值时)，重采样模块602前进到新的桶。例如，重采样模块602将原始笔划样本806添加到第一桶808，而无需超过第一桶的阈值(其在该情况下为1.0)。重采样模块602随后将另一原始笔划样本810添加到第一桶808，而再次无需超过阈值。但随后假设重采样模块602发现通过将另一笔划样本812添加到第一桶808，它将超过阈值。作为响应，重采样模块602添加笔划样本812作为第二桶814的第一条目。该过程按以上描述的方式继续，按与用户产生原始手写802的零碎方式来处理原始笔划样本。

在到达原始手写802的直线部分816之际，重采样模块602将发现它可使相对大量的原始笔划样本纳入单个桶中。结果，重采样手写804可使单个重采样笔划样本818专用于原始手写802的直线部分816。接着假设，在原始手写的时刻820处，用户将指示笔提离输入设备104的书写表面。因此假设，在时刻822，用户将指示笔再次应用于书写表面。重采样模块602为这两个事件发起对新的重采样笔划样本的创建，如重采样手写804中出现的重采样笔划样本824、826所指示的。还应注意，重采样模块602在用户的指示笔不与书写表面接触时不使任何桶递增。

重采样模块602可使用基于曲率的重采样来高效地表示手写。例如，重采样手写804包括与原始手写802相比更少的笔划样本。通过比较，考虑恒定距离采样技术，其中重采样模块602将为原始手写802所经过的每一固定距离d创建新的笔划样本。若重采样模块602使用了该技术，则该重采样模块会创建与以上描述的基于曲率的重采样技术相比更多的重采样笔划样本(这取决于d的值)。

图9传达了使用基于曲率的重采样的另一优点。此处，TFM106产生重采样笔划样本来表达第一记号902和第二记号904。记号(902、904)表示字符“abc”的不同实例。即，尽管从高级语义观点来看记号(902、904)表达相同字符，但从图形观点来看这些字符还按各种方式彼此改变。与使用例如恒定距离重采样相比，TFM106使用基于曲率的重采样可更高效地捕捉两个记号(902、904)之间的相似性。这使得第一记号902中的笔划样本将更有可能与第二记号904中的笔划样本匹配(例如，使得第一笔划902中的第x个笔划样本将与第二笔划904中的第x个笔划样本匹配)。

此外，为了进一步降低这些记号(902、904)之间的差别，TFM106可将其笔划幅度标准化。这降低了记号(902、904)之间的尺寸变化，例如使得可高效地将字符“abc”的大型版本与字符“abc”的较小版本进行比较。即，TFM106使用r_k/η_k为记号中的每一样本产生了经标准化的幅度值其中η_k被计算成记号中的各笔划幅度的高斯加权移动均值。在以下描述中，幅度r_k可以按以上描述的方式(但没有对该方式进行明确陈述)来标准化。

记号(902、904)之间的相似性通过比较其描述符(906、908)来进一步证明。一般来说，描述符指代描述记号的方式。在图9的情况中，SPS102将每一记号表示成两个直方图，诸如将第一记号902表示成第一直方图910和第二直方图912。两个直方图(910、912)沿着其水平轴表达第一记号902的各样本，即从第一样本φ_i到最后一个样本φ_i+n。第一直方图910的垂直维度表达每一样本的取向(θ)。第一直方图910中的每一数据点的密度表达样本的幅度值(r)。此处，暗点对应于相对高的r幅度。第二直方图912中的每一数据点的密度表达压力值(p)。此处，暗点对应于相对低的压力，例如最暗的点指示用户已经将指示笔提离输入设备104的书写表面。(注意图9仅描绘了直方图中的几个密度阴影以方便说明，但在实际实践中，直方图可表达附加的密度梯度。)第二描述符908也由两个直方图(914、915)组成，这两个直方图表达与以上所述的直方图(910、912)相同的信息。

更一般地，图9中的直方图使用时间表示来描述记号(902、904)。即，当用户在输入设备104的书写表面上进行书写时，以零碎方式逐样本地创建每一记号。这意味着每一直方图的水平轴是一连串时间实例的代理。

总体上，观察到第一描述符906类似于第二描述符908。这部分归因于使用基于曲率的重采样来表示手写。例如，考虑其中重采样模块602使用恒定距离重采样来为图9中示出的字符“abc”的两个实例产生描述符的替换情况。这些记号的描述符(未示出)不会展现出与图9中描绘的相同的相关性程度。

通过该描述，TFM106还可使用除基于曲率的采样以外的其他类型的重采样策略(包括恒定距离采样策略)来实现。此外，在使用曲率采样的那些情况下，重采样模块602可使用除图7中示出的过程702之外的其他用于定义样本的技术。

C.相似性评估模块

图10示出了相似性评估模块(SAM)110的一个实现。如章节A中记录的，SAM110确定新记号和先前记号之间的相似性。新记号对应于TFM106已经定义的最新近的记号，而先前记号对应于TFM106先前已经定义的记号。数据存储108存储这些先前记号。

一般来说，SAM110可通过形成新记号的描述符和先前记号的另一描述符来将该新记号与先前记号进行比较。SAM110可随后使用任何技术来对这两个描述符进行比较。如果这两个描述符之间的差小于指定阈值，则SAM110可推断出该新记号类似于先前记号。

在一个实现中，SAM110可通过将新记号与每一个体记号进行比较来起作用。在另一实现中，聚类管理模块1002可形成记号的聚类1004。每一聚类包括先前已被评估为彼此相似的记号集合。每一聚类还包括聚类表示，诸如聚类均值Ψ。聚类均值Ψ表示聚类内的记号的平均值。在该实现中，SAM110通过将新记号与每一聚类表示而非各个先前记号进行比较来起作用。

聚类管理模块1002还可将新记号添加到其最接近地匹配的任何聚类中。聚类管理模块1002可通过更新聚类均值以考虑新记号的贡献(例如，通过对聚类均值与新记号求平均以产生新的聚类均值)来执行该任务。替换地，如果不存在足够相似的现有聚类，则聚类管理模块1002可创建新聚类。最初，新聚类包括对应于新记号的单个成员。

SAM110可采用任何方案来确定两个记号之间(例如，新记号和记号均值之间)的相似性。在一个方案中，SAM110包括粗略相似性确定模块1006和精细相似性确定模块1008。粗略相似性确定模块1006使用时间分析来对两个记号之间的相似性作出第一级评估。该时间分析得到例如与同新记号匹配的候选聚类均值集合(如果有的话)相对应的候选记号集合。精细相似性确定模块1008使用空间分析来验证每一候选令牌是否实际上是对新记号的合适匹配。

图11示出归纳SAM110的操作的过程1102。在框1104，SAM110确定新记号和每一先前记号(或聚类均值)之间的粗略相似性以产生候选记号集合。在框1106，SAM110使用空间分析来验证每一候选记号是否实际上是对新记号的合适匹配。框1104和1106中的各个体子步骤将在此章节的稍后时刻处描述。

在一个实现中，SPS102可为它执行的所有相似性比较执行框1104和1106中的操作，这些相似性比较包括其中SPS102出于更新聚类的目的而使用相似性分析来寻找最接近匹配聚类的情况A，以及其中SPS102出于美化新记号的目的而使用相似性分析来寻找相似聚类集合的情况B。在另一实现中，对于情况A，SPS102可执行框1104，但不执行框1106。

图12示出归纳聚类管理模块1002的操作的过程1202。在框1204，聚类管理模块1002接收新记号。在框1206，聚类管理模块1002依赖于SAM110来确定新记号和各聚类表示(例如，各聚类均值)之间的相似性。在框1208，聚类管理模块1002(仅使用框1104中的分析或使用框1104和1106的两阶段的分析)确定是否存在在预定阈值τ内与新记号匹配的任何聚类。如果存在至少一个这样的聚类，则在框1210，聚类管理模块1002可使用TRM112(按以下描述的方式)将新记号合并到最接近匹配的聚类中。在另一实现中(未示出)，聚类管理模块1002可潜在地将该记号添加到满足以上相似性阈值的两个或更多个聚类中。

替换地，在框1212，假设聚类管理模块1002确定没有聚类与新记号合适地相似。在该情况下，聚类管理模块1002创建新聚类来表示新记号。该新聚类最初包括对应于新记号的一个成员。

图11中的框1104与图13的示例一起示出用于对要比较的每一对记号执行粗略级别时间分析的一个技术。SAM110通过使用单个描述符1302来表达每一记号开始。那个描述符1302对应于图9中示出的直方图910类型；即，描述符1302描述作为样本(φ)的函数的取向(θ)和幅度(r)值。在框1104的步骤(1.1)，SAM110将单个描述符1302分成两个分开的描述符(1304、1306)。第一描述符1304描述针对指示笔与显示表面接触时的时间的笔划样本。第二描述符1306描述针对指示笔不与显示表面接触时的时间的笔划样本。

在步骤(1.2)，SAM110例如通过使用高斯函数修改两个描述符(1304,1306)中的值来在时间维度中模糊化这两个描述符(1304、1306)。这得到经模糊化的描述符(1308、1310)。在步骤(1.3)，SAM110在经模糊化的描述符(1304、1306)中采用幅度的对数。由于小笔划样本可与大笔划样本一样在视觉上显著，因此执行该操作；该操作有助于均衡跨比例的改变。在步骤(1.4)，SAM110通过时间居中高斯来对步骤(1.3)的结果进行加权。所得的经处理的落笔和提笔描述符可随后被组合以形成单个矢量。

SAM110对要比较的每一记号执行以上描述的操作。更具体地，考虑正将新记号与聚类均值进行比较的情况。SAM110对新记号并分开地对聚类均值执行以上描述的处理。这最终得到供比较的两个矢量。在步骤(2)，SAM110随后使用任何比较技术来比较这两个矢量，诸如通过计算这些矢量之间的距离L2。通过对新记号和聚类均值的每一配对执行该相同的过程，SAM110可标识出在新记号的指定阈值距离内的聚类集合(如果有的话)。这得到零个、一个或更多个候选记号以供在过程1102的框1106中进行验证。

图11中的框1106与图14的示例一起示出用于对要与新记号进行比较的每一候选记号执行精细级别空间分析的一个技术。在步骤(1.1)，SAM110通过形成要比较的每一记号的低分辨率描述符(诸如图14中示出的低分辨率描述符1402)来开始。换言之，SAM110提供对记号的空间渲染，从而重复其如由用户画出的外观。在步骤(1.2)，SAM110用所渲染的笔划各自距记号的中心的相应时间距离来对所渲染的笔划的强度进行加权。换言之，在绘出记号时，用户按特定时间次序产生笔划；SAM110对在该过程的开始和结束处作出的笔划加权最少，并对在该过程的中间处发生的笔划加权最多。在步骤(1.3)，SAM110在空间上将步骤(1.2)的结果模糊化几个像素以例如产生经模糊化的描述符1404。在步骤(1.4)，SAM110使标记内容位于步骤(1.3)产生的经模糊化的描述符的中心，例如使得记号的中间被放置在描述符的中间。SAM110对要比较的每一记号对执行上述过程以供验证。例如，SAM110可对新记号和通过在框1104执行的粗略级分析标识出的特定聚类均值执行上述过程。这得到针对正被比较的两个相应记号的两个描述符。在步骤(2)，SAM110随后使用任何技术(诸如通过形成距离L2)来计算每一描述符对之间的距离。更具体地，SAM110可形成在第一描述符中的每一位置与第二描述符中的每一相应位置之间的差，从而从整体上得到多个差。相似性评估模块对这些差进行求和以生成最终距离测量q。在步骤(3)，SAM110可使用距离测量q上的正态分布(例如，使用等式λ＝exp(-q/2σ²))来形成最终置信分数λ。

SAM110执行以上描述的精细粒度空间分析(在框1106)，因为粗略粒度时间分析(在框1104)无法总是足以标识出相似的记号。图14的示例证明了这一点。如那里所示出的，双“e”记号1406和“a”字符记号1408得到相应的时间描述符(1410、1412)。通过比较，两个双“e”记号(1414、1416)得到相应的时间描述符(1418、1420)。观察者可明白双“e”记号1406与“a”字符记号1408不是良好匹配。然而，描述符1410和1412之间的区别不比描述符1418和1420之间的区别大很多。换言之，时间分析没有清楚地展现出双“e”记号1406和“a”字符记号1408之间的差。为了解决这一缺点，SAM110执行上述在描述符之间的空间比较。事实上，空间描述符1402(对应于双“e”记号1406)和空间描述符1422(对应于“a”字符记号1408)之间存在相对于空间描述符1424和1426(对应于两个双“e”记号1414和1416)之间的差而言显著的差。

如上所述，SAM110可将每一新记号与每一个体先前记号进行比较。或者为了更高效，SAM110可将每一新记号与每一聚类均值进行比较。但是使用聚类均值的比较本身可表示资源密集型计算。为了解决该问题，本章节的其余部分描述用于进一步加速搜索以寻找到相似的先前标记的一种技术。

首先考虑图15的示例。该图示出了当前记号(Φ_当前)，其表示SPS102已经处理的最新近记号。该当前记号之前是先前记号(Φ_先前)。如上所述，当前记号有30个样本与先前记号一样，其对应于部分1502。即，新记号添加了先前记号中不存在的一个样本1504，并省略了先前记号中存在的一个记号1506。进一步假设SAM110已经确定先前记号与特定聚类均值Ψ_最接近最相似。如果Φ_先前和现有聚类均值之间不存在良好匹配，则将Φ_先前分配给新聚类，其中Ψ_最接近＝Φ_先前。

SAM110可预先计算类似于Ψ_最接近的聚类。例如假设聚类管理模块1002由于不存在足够类似于Φ_先前的现有聚类而被迫为Φ_先前定义新聚类的情况。在创建了新聚类后，SAM110将部分1502与其他现有聚类均值进行比较，并且省略在这些其他聚类均值中的末端样本(例如对应于样本1504)。例如，假设当将末端样本从聚类均值Ψ_a、Ψ_b和Ψ_c中移除时，SAM110确定部分1502类似于这些聚类均值。SAM110随后将该关联存储在例如查找表等中。即，该关联使Ψ_最接近与聚类均值Ψ_a、Ψ_b和Ψ_c链接。随后，在计算当前聚类和聚类均值(Φ_当前)之间的相似性的时间到来时，SAM110可将当前记号与相关的聚类均值Ψ_a、Ψ_b和Ψ_c进行比较，而非与整个聚类均值集合(其可以有很大的数目)进行比较。该比较通过考虑这些相关聚类均值中的每一个的完全版本(例如通过现在将这些聚类均值的末端样本包括在该比较中)来作出。

图16示出用于建立记号和相关聚类集合之间的关系(例如在以上情况下，通过建立部分1502及其相关聚类均值(Ψ_a，Ψ_b，Ψ_c)的集合之间的关系)的过程1602。过程1602由聚类管理模块1002使用SAM110来执行。在框1604，聚类管理模块1002接收新记号(Φ_当前)。在框1606，聚类管理模块1002确定新记号是否与现有聚类之一足够相似。如果如此，则在框1608，聚类管理模块1002将新记号与最接近匹配聚类的聚类均值合并。由于该聚类已经存在，因此不必计算与该最接近匹配聚类相关的其他聚类集合；即该假设是聚类管理模块1002已经在例如该最接近匹配聚类最初被创建时为其确定了该相关集合。

替换地，在框1610，假设新记号不与任何现有聚类匹配。作为响应，聚类管理模块1002创建与新记号相关联的新聚类。在框1612，聚类管理模块1002随后尝试寻找到与新记号相关的其他聚类的集合(其中更精确地说，比较在部分1502和每一聚类均值的省略该聚类均值的末端样本的版本之间进行)。在一个方案中，聚类管理模块1002可通过将新记号与每一个现有的个体聚类均值进行比较来执行该任务。在另一方案中，聚类管理模块1002可通过随机地采样指定数目γ的聚类均值来执行该任务。假设在该随机搜索中，聚类管理模块1002发现了与新记号相关的聚类均值t。查找表将展示出聚类t，并进而与预定聚类集合(例如，聚类f、g等)相关。基于该知识，聚类管理模块1002随后例如通过将新记号与聚类均值f、聚类均值g和聚类均值h等等进行比较来确定新记号与发现的每一相关记号之间的相似性。在框1614，聚类管理模块1002通过存储将已经创建(以保持新记号)的新聚类与所发现的相关聚类均值的集合链接的索引来存储在框1612建立的关系。过程1602作为整体来考虑会建立聚类的交叉链接集合，其中查找表将每一聚类与相关的聚类集合(如果有的话)链接。

图17示出用于应用经由图16的过程1602习得的关系的过程1702。在框1704，SAM110接收新记号(Φ_当前)，该新记号在先前记号(Φ_先前)后面。在框1706，SAM110标识与先前记号匹配的聚类均值(Ψ_先前)。(注意，SAM110已在先前步骤中在先前记号构成当前记号时确定了该聚类均值。)在框1708，SAM110标识已被预先确定为与Ψ_先前相似的相关聚类均值的集合。在框1710，SAM110将新记号与标识出聚类均值的集合中的每一个聚类均值进行比较。

D.记号细化模块

图18示出了图1的记号细化模块(TRM)112的一个实现。TRM112接收新记号和由SAM110标识出的相似记号中的每一者。考虑将仅合并两个记号的简要情况。对齐确定模块1802将第一记号的各样本与第二样本的各相应记号进行比较。这会产生相关的记号。记号混合模块1804随后将相关记号彼此混合。

在一个应用中，SPS102在TFM112上调用以将新记号与被确定为与新记号最接近地匹配的聚类均值混合。SPS102在它操作以更新其存储在数据存储108中的聚类集合时执行该任务。在另一应用中，SPS102在TRM112上调用以将新记号与在某一阈值相似性水平内已被确定为与该新记号匹配的聚类均值集合混合。SPS102在其寻求基于先前相似记号来细化新记号的外观时执行该任务。

图19示出归纳TRM112的操作的过程1902。在框1904，TRM112接收新记号。在框1906，TRM112从SAM110接收一个或多个相似记号。在框1908，TRM112(使用以下描述的技术)将每一个先前记号与新记号对齐。在框1910，TRM112可将新记号的样本与(诸)相似的先前记号中的相关样本混合。

更具体地，TRM112可通过把将对平均值有贡献的每一端点从极坐标转换到笛卡尔坐标来执行框1910的操作，例如使用x_k＝r_kcos(θk)和y_k＝r_ksin(θ_k)，其中(r_k，θ_k)对应于要被求平均的样本之一。TRM112可随后将(与有贡献的样本相关联的)所有x值一起求平均以提供所得的平均样本的平均值x，并且对于各y值进行相似的处理。TRM112可随后将所得的平均样本点转换回成极坐标。TRM112可通过对各个体p值求平均来计算经混合的压力值，其中每一个体p值被加权其相应样本的幅度(r)。注意，在出于美化新记号的目的来执行混合时，TRM112可执行附加计算，这些附加计算在图19中没有指定但在以下将被描述。

图20示出用于确定第一记号2002和第二记号2004中的样本之间的相关性的一种技术。第一记号2002用呈现作为样本(φ)的函数的取向(θ)和幅度(r)值的第一描述符2006和呈现作为样本(φ)的函数的压力(p)值的第二描述符2008来表示。同样，第二记号2004用第一和第二描述符(2010、2012)来描述。对齐确定模块1802首先计算成本矩阵2014。成本矩阵中的每一单元由标识第一记号2002中的样本的第一索引和标识第二记号2004中的样本的第二索引来定义。该单元具有描述在第一和第二记号中标识出的各样本之间的差(ω)的值。在一种情况下，该差可被计算成：

ω＝Δ_r+Δ_θ+δ_p

在该等式中，值Δ_r对应于两个记号的幅度之间的绝对差，例如Δ_r＝|r_记号1-r_记号2|。值Δ_θ对应于两个记号的取向值之间的绝对角距离，例如Δ_θ＝|θ_记号1-θ_记号2｜.如果p_记号1＝0且p_记号2＝0或者如果p_记号1>0且p_记号2>0，则δ_p＝1；否则，δ_p的值为1。对齐确定模块1802随后通过成本矩阵2014寻找出从单元c₁₁到单元c_nn的最低成本路径2016。在选择路径时，对齐确定模块1802可在每一步骤{(0,1)、(1,0)和(1,1)}处从三个移动中进行选择，这三个移动对应于：(a)从左移到右→；(b)以向上的方向移动↑；以及(3)对角线移动到目的地单元的每一移动均具有与其相关联的特定成本值，该特定成本值被定义为ω+ξ，其中小成本值与大成本值相比更优选。以上定义了值ω；在该上下文中，ω测量由目的地单元的索引标识的两个记号之间的相似性。值ξ通过向对角线移动分配为0的值并向其他情况分配很小的正数值(例如，0.2)来支持对角线移动。对齐确定模块1802可使用任何技术(诸如但不限于动态编程技术)来计算路径2016。

记号混合模块1804可(出于笔划美化的目的)按以下方式将新记号与相似的先前记号混合。首先，考虑以下观察：新记号中的任何给定笔划样本φ_i可实际上表示n个不同的记号中的一样本，即Φ_i-n到Φ_i(也即假设φ_i为“原来的”至少一个记号长度)。这些记号Φ_j(其中j∈[i-n，i])中的每一个具有其自己的拥有相应的置信分数λ_jk(k∈m_j)的候选聚类匹配m_j的集合。置信分数λ_jk指示记号φ_j与聚类均值ψ_k匹配的程度，其可使用距离L2上的正态分布来计算。对于聚类均值ψ_k，样本φ_l∈Ψ_k(其中l＝i-j)将对笔划样本φ_i的细化有贡献。向样本φ_l分配的权重w_ijk可使用下式计算：

在该等式中，指代例如具有均值n/2和标准差σ＝n/6的正态分布。对高斯加权的使用确保在细化时各记号的贡献之间的平滑转变。

使用以上权重，记号混合模块1804现在可如下计算经细化的端点的笛卡尔值

$>{\tilde{x}}_i=\frac{x_i+{\Sigma }_{j\in \left[i-n,i\right]}{\Sigma }_{k\in m_j}{w}_{ijk}{s}_k{x}_l}{1+{\Sigma }_{j\in \left[i-n,i\right]}{\Sigma }_{k\in m_j}{w}_{ijk}{s}_k}$>

在该等式中，xi指代要细化的新记号的x坐标值，并且x_l对应于聚类均值中对新记号的细化有贡献的坐标值。这些笛卡尔值可按以上描述的方式从存储的极坐标中计算出。值w_ijk对应于按上述方式计算出的加权因子。值s_k反映聚类k的大小，例如对应于聚类的大小的平方根；因此以上等式将较高的权重分配给较大的聚类。笛卡尔坐标的经细化的值和压力的经细化的值可使用与上述针对描述的相似的方式来计算。具体地，记号混合模块1804就一直等待，直到样本为在对其进行细化之前的“原来的”至少一个记号长度。

E.其他应用

图21示出搜索功能2102的一个实现，取代细化应用或作为其补充，该搜索功能表示SPS102的另一应用。搜索功能2102包括用于创建和管理索引的索引管理模块2104。数据存储2106存储索引。更具体地，索引管理模块2104存储先前遇见的记号和这些记号在文档内的相应位置之间的链接。例如，假设用户在过去已书写了单词“Sue”若干次。SAM110可标识包含与该单词相关联的记号的一个或多个聚类。索引管理模块2014还将描述这些记号在用户先前已创建的文档内的位置的信息存储在索引中。

搜索模块2108可响应于用户的输入记号而提供任何搜索结果。例如，假设用户再次输入单词“Sue”。搜索模块2108可首先从SAM110接收指示与单词“Sue”相关联的(诸)记号的信息。搜索模块2108可随后与索引进行交互以确定单词“Sue”的先前实例在用户先前已创建的文档中的相应位置。搜索模块2108可随后按任何方式来向用户通知这些先前的出现，诸如通过显示包含单词Sue2112的文档2110并按任何方式将那个单词Sue2112突出显示在那个文档2110中。

图22示出自动完成功能2202的一个实现，取代细化应用或作为其补充，该自动完成功能表示SPS102的另一应用。自动完成功能2202包括预测一个记号将跟随另一记号的可能性的预测确定模块2204。自动完成功能2202可按任何方式来执行该任务，例如通过对训练语料库内的记号的并发性进行计数并随后基于那些计数值来训练n元模型。数据存储2206可存储指示由预测确定模块2204作出的预测的预测信息。

自动完成模块2208基于存储在数据存储2206中的预测信息来执行自动完成操作。假设例如用户输入了具有大写字母“B”的单词“Best(最佳)”2210。SAM110可通过将与该单词相关联的记号与先前记号匹配来解释该单词。自动完成模块2208从SAM110接收匹配记号信息。作为响应，它基于数据存储2206中的预测信息来确定可能跟随组成单词“Best”的记号的那些记号(如果有的话)。假设用户在过去在结束他或她手写的信时已书写了短语“Bestregards(祝好)”许多次。自动完成模块2208可因此将组成单词“Regards”的单词的记号标识成跟随单词“Best”的可能单词。”

自动完成模块2208可随后按任何方式向用户呈现其发现，诸如通过使词“Regards”2212紧接单词“Best”显示。用户可选择单词“Regards”以将该单词正式地添加到他或她的书写中，或者继续书写以有效地忽略自动完成功能2202的推荐。

以上作为示例而非限制描述了搜索功能2102和自动完成功能2202。其他应用可利用SPS102的上述特征。

图23示出提供搜索功能2102和自动完成功能2202的操作的概览的过程2302。在框2304，SPS102接收新记号。在框2306，SPS102标识与新记号相似的先前记号(如果有的话)。在框2308，SPS102基于在框2306标识出的(诸)相似记号来执行搜索操作和/或自动完成操作。

F.代表性计算功能

图24表示图1的SPS102的独立实现。即，在该实现中，本地计算装备2402可实现SPS102的所有方面。图24通过指示本地计算装备2402包括本地SPS功能2404来展示这一点。本地计算装备2402可由个人计算机、计算机工作站、膝上型计算机、平板型计算机、游戏控制台、机顶盒设备、媒体消费设备、智能电话等等来实现。

图25示出了SPS102的分布式实现，其中SPS功能分布在本地计算装备2502和远程计算装备2504之间。即，本地计算装备2502可实现本地SPS功能2506，而远程计算装备2504可实现远程SPS功能2508。本地计算装备2502可使用以上参考图24描述的任何技术来实现。远程计算装备2504可例如使用一个或多个服务器及相关联的数据存储来实现。通信机制2510可将本地计算装备2502与远程计算装备2504连接起来。通信机制2510可使用局域网、广域网(例如，因特网)、点对点连接等等或其任何组合来实现。

例如，在一个场景中，远程SPS功能2508可维护存储先前记号的数据存储108。远程SPS功能2508可将先前记号下载到本地SPS功能2506中以供本地SPS功能2506在分析手写时使用。在另一情况下，远程SPS功能2508也可执行如上所述的SPS102的一个或多个处理功能。例如，本地SPS功能2506可将其大多数资源密集型计算卸载到远程SPS功能2508。

图26阐述了可以被用来实现上文所描述的功能的任何方面的说明性计算功能2600。例如，图26中示出的计算功能2600类型可被用来使用图24的功能、图25的功能或某个其他功能来实现图1的SPS102的任何方面。在一种情况下，计算功能2300可对应于包括一个或多个处理设备的任何类型的计算设备。在所有情形中，计算功能2300表示一个或多个物理且有形的处理机制。

计算功能2600可包括诸如RAM2602和ROM2604之类的易失性和非易失性存储器，以及一个或多个处理设备2606(例如，一个或多个CPU，和/或一个或多个GPU等等)。计算功能2600还可任选地包括诸如硬盘模块、光盘模块等等之类的各种介质设备2608。当(诸)处理设备2606执行由存储器(例如，RAM2602、ROM2604或在别处)维护的指令时，计算功能2600可执行上文所标识的各种操作。

更一般地，指令和其它信息可以被存储在任何计算机可读介质2610上，计算机可读介质包括但不限于静态存储器存储设备、磁存储设备、光存储设备等。术语计算机可读介质还涵盖多个存储设备。在多种情况下，计算机可读介质2610都表示某种形式的物理和有形的实体。术语计算机可读介质还包括传播信号，例如经由物理管道和/或空气或其他无线介质等来传送或接收的。然而，特定术语“计算可读存储介质”和“计算机可读介质设备”明确地排除传播信号本身，但是包括所有其他形式的计算机可读介质。

计算功能2600还包括用于接收各种输入(通过输入设备2614)，以及用于提供各种输出(通过输出设备)的输入/输出模块2612。说明性的输入设备包括键盘设备、鼠标输入设备、触摸屏输入设备、数字化垫、姿势输入设备、语音识别机制、平板或墙壁投影输入机制等。一种特定输出机制可包括呈现设备2616及相关联的图形用户界面(GUI)2618。计算功能2600还可以包括用于通过一个或多个通信管道2622与其他设备交换数据的一个或多个网络接口2620。一条或多条通信总线2624将上述组件通信地耦合在一起。(诸)通信管道2622可以按任何方式来实现，例如，通过局域网、广域网(例如，因特网)等等或其任何组合来实现。(诸)通信管道2622可包括可由任何协议或协议的组合管理的硬连线的链路、无线链路、路由器、网关功能、名称服务器等等的任何组合。

作为替代或除此之外，前述各节中所述的任何功能可至少部分地由一个或多个硬件逻辑组件来执行。作为示例而非限制，计算功能可使用以下的一个或多个来实现：现场可编程门阵列(FPGA)；专用集成电路(ASIC)；专用标准产品(ASSP)；片上系统(SOC)；复杂可编程逻辑器件(CPLD)等等。

作为结束语，本文所述的功能性可采用各种机制来确保该功能性所维护的用户数据(如果有的话)的私密性。。例如，该功能可允许用户明确地选择进入(以及明确地选择退出)功能的供应。功能还可提供适用的安全机制来确保用户数据的私密性(如数据净化机制、加密机制、口令保护机制等)。

此外，说明书在说明性挑战或问题的上下文中描述了各种概念。这种说明方式不构成其他人以此处所指定的方式理解和/或明确表达挑战或问题的许可。此外，所要求保护的主题也不仅限于解决提到的挑战/问题中的任意或全部的实现。

尽管用结构特征和/或方法动作专用的语言描述了本主题，但可以理解，所附权利要求书中定义的主题不必限于上述具体特征或动作。相反，上述具体特征和动作是作为实现权利要求的示例形式公开的。