用于资源约束和其它设备的统一可搜索存储

摘要

本公开描述了数据索引和搜索服务，其本地驻留在计算设备(例如，移动电话)上并且可以托管用于设备上的多个应用的数据。通过集中数据的存储以及搜索和查询功能，可以通过服务来执行统一搜索查询。

说明书

相关申请的交叉引用

本申请要求2013年1月16日提交的美国临时申请序列号61/753,152和2013年8月20日提交的美国申请序列号13/971,240的权益，它们通过引用方式并入。

技术领域

本公开涉及用于资源约束设备的统一可搜索存储。

背景技术

搜索程序可以允许用户执行例如用户的电子邮件、计算机文件、音乐、照片、聊天和查看的Web页面的文本搜索。当最初安装在设备(例如，台式个人计算机)上时，软件程序可以为计算机中的文件编索引。在初始索引完成之后，软件可以继续按需为文件编索引。然后，编索引的文件可以由用户搜索，并且结果可以例如在web浏览器中返回。

在设备可以具有例如相对慢的中央处理单(CPU)、有限的随机存取存储器(RAM)和/或有限的盘存储的意义上，其存储各种类型的用户可能希望搜索的文件的一些设备是资源约束的。在这样的资源约束环境中，更新存储和索引可能是低效的，从而导致高后台CPU使用和太多盘活动。因此，一些解决方案并不容易伸缩到要存储和搜索的期望数据量。缺乏可伸缩性可能使得难以(如果不是不可能的)包括诸如横跨多个应用和数据库的快速统一搜索和统一关键字和实体建议之类的特征。

发明内容

本公开描述了数据索引和搜索服务，其本地驻留在设备(例如，移动电话)上，并且可以托管用于设备上的多个应用的数据。通过集中数据的存储以及搜索和查询功能，可以通过服务执行统一搜索查询，而不需要在一些情况下启动多个应用和打开多个数据库。

例如，根据一个方面，计算设备包括用户界面和驻留在计算设备中的应用，用户界面包括搜索框，其中每个应用包括相应内容提供者。计算设备包括索引管理器、数据索引和搜索服务和盘支持的存储装置(例如，快闪存储装置)，数据索引和搜索服务驻留在计算设备中并且提供到索引管理器的进入点。数据索引和搜索服务可操作为获得来自与应用中的相应应用相关联的内容提供者的数据。索引管理器为来自内容提供者的数据编索引，并且将编索引的数据存储在盘支持的存储装置中。数据索引管理器包括查询处理器以处理从搜索框接收和从应用中的任何应用接收的搜索查询的执行。查询处理器通过搜索盘支持的存储装置中存储的编索引的数据并且返回基于搜索的结果来处理搜索查询的执行。

各种实施方式包括以下特征中的一个或多个。例如，在一些实施方式中，响应于接收来自应用中的特定应用的搜索查询，数据索引和搜索服务返回仅关于与应用中的特定应用相关联的语料库的结果。另一方面，响应于接收来自搜索框的搜索查询，数据索引和搜索服务可以返回关于与应用相关联的所有语料库或者关于语料库的子集的结果。

在一些实施方式中，盘支持的存储装置存储第一索引和第二索引，第一索引具有将来自特定应用的文档中包含的项映射到项标识符的字典，第二索引具有将项映射到项标识符的字典和到索引文件中的偏移。数据的编索引可以发生例如在所述第一索引中，第一索引可以周期性地合并到第二索引中。字典可以被实现为例如文件支持的字典树。

在一些情况下，响应于来自应用中的特定应用的向索引和搜索服务注册的请求，索引和搜索服务执行来自特定应用的数据的编索引。索引和搜索服务还可以响应于由应用中的特定应用索引的请求，执行来自特定应用的数据的编索引。

在另一方面中，描述了在计算设备上索引和搜索数据的方法。例如，在一些实施方式中，方法包括：将驻留在计算设备上的第一应用绑定到驻留在计算设备上的索引和搜索服务，以及向索引和搜索服务注册与第一应用相关联的语料库和内容提供者。由索引和搜索服务为来自与第一应用相关联的文件的数据编索引，并且编索引的数据被存储在设备上的盘支持的存储装置中。然后索引和搜索服务可以用于执行来自第一应用的搜索查询。关于驻留在计算设备上的其它应用，可以执行相似的处理。

一些实施方式包括以下优点中的一个或多个优点。例如，将所有应用索引存储在一个地方(即，在同一盘支持的快闪存储装置中)可以便于更快的通用搜索。此外，盘支持的存储装置可以是可伸缩的，并且可以提供例如用于预测应用的统计。数据索引和搜索服务可以相对快地执行搜索，并且可以使用具有相对小足迹的压缩存储。服务可以减少所要求的快闪写入的数目，并且可以允许写操作包括更大量的数据(例如，通过使用批处理)。

其它方面、特征和优点将从以下详细描述、附图和权利要求中变得容易理解。

附图说明

图1图示其包括设备上数据索引和搜索服务的计算设备的示例。

图2是图示使用数据索引和搜索服务的示例的流程图。

图3是图示使用数据索引和搜索服务的另一示例的流程图。

具体实施方式

本公开描述数据索引和搜索服务，其本地驻留在设备(例如，移动电话)上并且托管用于设备上的多个应用的数据。数据索引和服务可以提供高效的、集中式设备上(离线)搜索和文档存储服务，并且可以向设备上的其它应用提供开放式应用编程接口(API)。技术可以便于搜索设备中的所有语料库(或语料库的子集)，并且可以便于跨所有语料库(或语料库的子集)的关键字建议。此外，隐私模型被描述为确保来自一个语料库的数据(例如，建议和搜索结果)不会出现在旨在于另一语料库的搜索中。

例如，本文中描述的技术可以实现在各种类型的资源约束设备上，包括诸如移动电话、平板和个人数字助理(PDA)之类的手持式计算设备。技术还可以实现在诸如台式个人计算机、膝上型计算机之类的其它计算设备上。

如图1所示，计算设备(例如，移动电话)具有图形用户界面，图形用户界面包括其中设备的用户可以输入搜索项的搜索框12。设备还存储其可以在设备上执行的一个或多个应用(例如，应用A、应用B和应用C)。这样的应用的示例是驻留在设备上的电子邮件应用。数据索引和搜索服务14从与每个应用A、B、C相关联的相应客户端内容提供者15拉取数据(例如，文档)，将数据存储在相应语料库18中，并且为其编索引。例如，语料库18可以存储在计算设备上的快闪存储20中的文件中。

索引和搜索服务14担任到索引管理器22的进入点，其实现绑定器API38、处理来自客户端应用的内容同步、以及封装其中后台处理发生的线程。索引管理器22包括其管理语料库18的文档存储管理器26以及其处理从搜索框12或者从客户端应用A、客户端应用B、客户端应用C之一接收的搜索查询的执行的查询处理器32。当应用需要获得搜索查询的结果时，应用向服务14委派搜索，而不是它自己执行搜索。

快闪存储20还存储简化索引28和主索引30。简化索引28可以在持续的基础上更新，并且具有将文档中包含的项映射到项标识符的字典(lexicon)34。主索引30担任其存储索引的其余部分的永久索引。简化索引28可以周期性地合并到永久索引30中，永久索引30具有将项映射到项标识符的字典36和到索引文件中的偏移。字典34、字典36、索引28、索引30和语料库18可以存储在盘支持的存储20中的单独文件中。例如，字典可以实现为由盘读取初始化的文件支持的字典树。

为了与服务14通过接口接合，应用A、应用B、应用C绑定到并且调用服务的接口定义语言应用编程接口(“IDLAPI”)38。然后，服务14使用应用A、应用B、应用C中的内容提供者15将应用的数据同步到它自己的存储20。文档可以通过其可以是客户端应用确定的任意字符串的统一资源标识符(URI)来引用。图2图示根据以下段落中讨论的特定实施方式的进一步细节。

最初，客户端应用A、客户端应用B、客户端应用C绑定到服务14(块102)。然后客户端应用调用关于语料库内容提供者15的授予URI许可函数，并且使用注册函数向服务14注册语料库和内容提供者(块104)。当客户端应用向服务14注册时，客户端应用提供服务14可以从其拉取内容的API的地址。然后，服务14使用客户端的内容提供者15来同步客户端的数据(块106)。同步处理的进一步细节描述在下面。当客户端应用具有用于服务14的新数据时，它调用请求索引函数(块108)，请求索引函数使得服务14从客户端的内容提供者15拉取更多数据(块110)。如下面描述的，客户端应用A、客户端应用B、客户端应用C可以发出关键字查询或者请求基于多字前缀的建议(块112)。查询和建议请求由服务14处理(块114)。

接下来描述同步处理的细节，同步处理是服务14插入来自其它应用A、B、C的文档并且使它们可搜索的机制。在一些实施方式中，服务14同步文档和标签(其是文档的性质)。客户端应用可以动态地改变向服务14提供的文档的属性，并且如下面讨论的，用户可以将搜索查询限于具有指定特征的文档。如上面提到的，文档可以通过不透明字符串URI唯一地引用，并且可以包含其也可以被索引的区段。例如，对于电子邮件应用，文档可以是单个消息，并且其区段可以包括“发件人”、“收件人”、“主题”和“主体”行。这样的文档可以包括例如以下标签：“收件箱”、“未读”或“已发送”。在一些实施方式中，文档中的总数据不可以超过预定量。对于超过这一长度的数据，文档的区段可以例如从该文档中的最长区段开始被截断。同步数据是由单调增加的动作序列号键控的表。然后服务14以该顺序应用那些动作。相应内容提供者15以单调增加的顺序返回序列号(例如到达时间戳)。

客户端应用A、客户端应用B、客户端应用C可以使用获取语料库状态函数来得到服务14对其数据的处理的可见性。例如，对于提交的任何数据，客户端应用可以安全地假定服务14不会再次请求该数据。然而，如果用户删除服务的数据，客户端应用将需要重新注册，在这种情况下，服务14将重新请求数据。客户端应用A、客户端应用B、客户端应用C可以注销语料库，这使得数据不再可访问；最终数据从快闪存储20被擦除。

以下段落解释服务14可以如何执行索引和搜索。通过注册语料库(例如，当应用A、应用B或应用C首次请求使用数据索引和搜索服务14时)或者通过请求索引，可以触发索引。轮询应用内容提供者、将数据写到快闪存储20和索引的任务以后台线程发生。当注册新语料库18时，通过服务14的索引立刻开始。当服务14接收关于现有语料库18的索引请求时，由于预期接收附加索引请求，服务14可以延迟索引(例如，一秒)。

在一些实施方式中，索引以多达20个文档或者一百个表示文档性质的标签批量发生。应用的内容提供者被请求针对给定查询最多返回这么多的文档。在这一批量被索引之后，另一索引任务可以立即在线程上重新调度。目标是减少对应用的内容提供者的大型查询，并且允许在需要索引的语料库18之间的公平性。索引可被执行至完成(即，直到没有来自语料库18中的任何语料库的文档仍然要索引)。

如上面提到的，文档存储管理器26管理语料库18。来自应用A、应用B、应用C之一、要存储和编索引在对应语料库18中的每个文档被压缩和附加到文件。删除部分和标签(即，文档性质)可以标记在通过文档标识符索引的位图中。文件还保持从语料库和URI到文档标识符的映射。

指示包含特定项的文档的项标识符—文档标识符对被附加到简化索引28和主索引30中的缓冲区中。然后，响应于建议或搜索查询，索引28、索引30可以返回与指定前缀匹配的所有项，或者可以返回根据指定项索引的文档标识符的列表。

索引文件28、30可以存储倒排列表。例如，在一些实施方式中，每个块保持用于倒排列表的字节数组的空闲列表，其可以以快闪页尺寸(例如，4K-8K)的块。倒排列表可以严格有序，例如从最近的文档往下(默认搜索结果排序顺序)，并且包含指示包含指定项的文档的“命中”(例如，文档标识符)。在一些实施方式中，倒排列表字节数组以固定尺寸来分配，大致以2的幂，多达1,000个命中，其中每个命中包含四个字节。如果项具有多于1,000个命中，块被链接在单链表中。

在一些实施方式中，查询以自由形式指定，并且可以具有最大许可长度。由一些实施方式支持的特殊操作符包括以下项：

搜索和建议查询通过绑定器API38到达并且在线执行。如图3所示，当服务14从搜索框12接收查询(块202)时，查询处理器32解析查询(块204)以确定语料库限制、标签限制和区段修改符(例如，电子邮件消息中的“收件人”行或者“主题”行)。当在服务14中接收查询时，简化索引28或主索引30之一中的缓冲区可以按项标识符进行排序(块206)。然后执行针对感兴趣项的二分搜索(块208)，并且获得包含搜索项的文档的文档标识符列表(块210)。对于来自搜索框12的搜索查询，服务14可以返回关于与应用相关联的所有语料库或者关于语料库子集的结果(块212)。

在一些实施方式中，查询处理器32查找简化索引28和主索引30两者中的项，从两个索引取回文档标识符的某个部分(直到参数“num_to_score”)，并且在多个项搜索的情况下，获得倒排列表的交集(或并集)。查询处理器32可以查找文档得分数组(即，诸如文档日期之类的由每个应用指示的得分)以将每个文档标识符映射到其得分，并且计算得分最高的文档标识符。这些文档标识符用于查找与文档标识符对应的内容。基于查询参数，针对每个文档返回文档内容的一部分。对于后续的查询，如果新的文档被编索引，则被添加至例如简化索引28的新项可以被单独排序，并且然后与先前排序的列表组合。

为了管理盘支持的快闪存储20，通过索引24访问存储20。新文档可以在它们被添加时立即附加至文档存储。新添加的文档然后被编索引。虽然索引和字典具有两段(即，主和简化)，索引发生在简化索引28中。在索引期间，所有字典和索引改变被写到简化索引28，直到调用刷新函数。索引命中被累积在文件中，但没有出现显式盘同步，直到调用刷新函数，这将简化索引28合并到主索引30中，擦除简化索引28，并且调用用于主索引30的fsync函数以提交缓冲数据。当达到简化索引限制时或者当定时器到期(例如，一天一次)时，可以调度刷新函数。

如上所述，当接收搜索查询时，查询处理器32搜索简化索引28和主索引30两者。在刷新操作期间，锁(lock)阻止搜索遍历部分写入的数据；因而，在刷新操作期间没有搜索可以发生。在一些实施方式中，刷新操作需要2-10秒，并且在要求刷新操作之前，约600个电子邮件消息可以缓冲在简化索引28中。

周期性地(例如，一周一次)或者当没有可用的盘空间时，执行压紧处理，以创建语料库文件18、索引文件28、30和字典文件34、36的新副本。所有删除的文档标识符被擦除，文档标识符空间被重新压紧，并且基于新文档标识符写入新索引。文档标识符首先按最高得分重新排序。新字典指向新索引中的倒排列表位置。在压紧完成之后，调用关于所有文件的fsync函数。然后使用新文件。在压紧期间没有索引发生，但是搜索可以使用旧索引进行。

优选地，数据完整性被保存，而不采取对盘同步函数的频繁、昂贵的调用。为了实现这一目标，在一些实施方式中使用以下性质。首先，索引像高速缓存；它不包含不可恢复数据，并且所有数据可以从语料库18重新创建，或者如果必要的话，从内容源(例如，与应用A、应用B或应用C相关联的内容提供者)重新同步。其次，优选对于不可能的情景具有更高恢复成本、但是对于普通情况具有低得多的平均资源使用(例如，盘写入)的解决方案。为了这一目的，数据可以在概念上分裂成“地面实况”数据和可恢复数据。如果地面实况数据丢失，其需要从内容源(即，客户端应用内容提供者)恢复，这往往是昂贵的。另一方面，可恢复数据可以从地面实况数据重构。地面实况数据可以包括例如文档存储、文档标识符映射器(将文档标识符映射到文档存储中的偏移)和标签位图。可恢复数据可以包括例如将URI映射到文档标识符的URI映射、将文档标识符映射到文档存储的文档得分表、以及索引、字典和项性质。地面实况数据是仅能附加的。因此，刷新的地面实况数据不能被功率损耗而损坏。

简化索引28和字典34可以使用读/写MAP_SHARED文件支持的数据结构，其包括更新循环冗余检验(CRC)。例如，每个随机写入数组可以通过CRC进行保护。当文件支持的数据结构接收onSleep回调时，它更新其CRC。两种策略可用于更新CRC。首先，小数目的随机更新可以缓冲和用于计算增量CRC，而大数目的更新可以清除缓冲区，并且退回到完整的CRC重新计算。在启动时，可以针对CRC检验一致性，以确保不一致的数据不被加载和使用。

主索引30和字典36可以使用其不会修改刷新之间的文件数据的MAP_PRIVATE只读文件支持的数据。因此，主索引30和字典36不受刷新之间的文件损坏的影响。在刷新期间，in_flushing比特同步到快闪存储20，刷新完成，并且然后比特未设置且主索引30重新同步到快闪存储20。在启动时，如果in_flushing比特被设置，则系统假定文件已损坏并且从地面实况数据重构它们。

一致性可以在索引管理器22之间协调，索引管理器22与客户端应用A、客户端应用B和客户端应用C同步内容并且同步索引实施方式。例如，在初始化时，索引管理器22将最后刷新状态向下传递到索引24。刷新状态包含最后刷新的(即，提交的)文档存储尺寸。索引24用自最后刷新点以来它能够成功恢复多少内容的指示来做出响应，并且用它在恢复区域中已看到的每语料库的最后序列号来做出响应。索引管理器22将其针对每个语料库18的最后序列号重置为最后刷新的序列号加上任何从索引24恢复的序列号。在这一文档存储初始化完成之后，索引被初始化。如果简化索引28损坏，自最后刷新以来看到的文档重新索引。如果主索引30损坏，整个索引重建。

由搜索时间和索引时间两者触及的任何数据结构可以受锁的保护。例如，在一些实施方式中，只要客户端应用A、客户端应用B、客户端应用C绑定到它或者后台线程有工作要执行，数据索引和搜索服务14保持活跃。当服务14不活跃时，索引管理器22接收到高速缓存服务14的“onSleep”事件。在一些情形下，框架(即，设备的操作系统)可以决定存在存储器压力并且在任何时间停止处理(以及索引管理器)。然而，通过高速缓存服务14，在用户想要执行背对背查询的情况下，数据和代码可以随时可用。

服务还创建例如每天在本地时间上午2:00运行的定期维护报警。如果例如设备的电池电量低(ACTION_BATTERY_LOW)，则维护警报每小时重试直到它成功。在一些情况下，维护每天执行刷新函数(即，盘提交)，并且每周或者当空闲空间小于允许空间的预定量(例如10％)时执行压紧。

通过集中数据的存储以及搜索和查询函数，可以由服务14执行统一搜索查询，而不需要启动多个应用和打开多个数据库。将所有应用索引存储在一个地方可以便于更快的通用搜索。在一些情况下，可以提供来自整个字典的快速、相关性得分(relevancy-scored)的建议。此外，存储20可以是可伸缩的，并且可以服务例如用于预测应用的统计。数据索引和搜索服务14可以相对快地执行搜索，并且使用具有相对小足迹的压缩存储。服务14可以减少所要求的快闪写入的数目，并且可以允许写操作包括更大量的数据(例如，通过使用批处理)。服务14可以通过使用文档的URI来取得文档。还有，在图示的实施方式中，服务14不具有耐久的写接口；因此，服务14决定何时提交数据，而不是客户端应用。

为了确保来自一个语料库的数据(例如，建议和搜索结果)不出现在旨在于另一语料库的搜索中，许可每个应用A、B、C具有仅针对其自己的语料库执行的搜索。相比之下，输入到搜索框12中的搜索查询可以关于所有语料库(或者指定的语料库子集)来执行。

本说明书中描述的主题的各个方面和功能操作可以实现在数字电子电路中，或者在计算机软件、固件或硬件(包括在本说明书中公开的结构和它们的结构等效物)中，或者在它们中的一个或多个的组合中。本说明书中描述的主题的实施例可以被实现为一个或多个计算机程序产品，即编码在计算机可读介质上的计算机程序指令的一个或多个模块，以用于由数据处理装置执行或者以控制数据处理装置的操作。计算机可读介质可以是机器可读存储设备、机器可读存储基板、存储器设备、实现机器可读传播信号的物质的组合物、或者它们中的一个或多个的组合。术语“数据处理装置”和“计算机”包含用于处理数据的所有装置、设备和机器，通过示例的方式包括可编程处理器、计算机、或者多个处理器或计算机。除了硬件，装置可以包括其创建用于考虑中的计算机程序的执行环境的代码，例如其构成处理器固件、协议栈、数据库管理系统、操作系统、或者它们中的一个或多个的组合的代码。

可以以任何形式的编程语言(包括编译性或解释性语言)来编写计算机程序(还称为程序、软件、软件应用、脚本或代码)，并且计算机程序可以以任何形式来部署，包括作为独立的程序或作为模块、部件、子例程、或其他适合用于在计算环境中使用的单元。计算机程序不必要对应于文件系统中的文件。程序可以被存储在保持其他程序或数据的文件的一部分中(例如，在标记语言文档中存储的一个或多个脚本)、存储在专用于考虑中的程序的单个文件中、或者存储在多个协调文件(例如，存储一个或多个模块、子程序或代码的部分的文件)中。计算机程序可以被部署为执行在一台计算机上或者执行在位于一个站点处或跨多个站点分布的并且通过通信网络互连的多台计算机上。

通过执行一个或多个计算机程序以通过对输入数据进行操作和生成输出来执行功能的一个或多个可编程处理器，可以执行本说明书中描述的处理和逻辑流程。处理和逻辑流程还可以通过专用逻辑电路(例如，FPGA(现场可编程门阵列)或ASIC(专用集成电路))来执行并且装置也可以被实现为专用逻辑电路。

适合于执行计算机程序的处理器包括(通过示例的方式)通用和专用微处理器两者、以及任何种类的数字计算机的任何一个或多个处理器。通常，处理器将接收来自只读存储器或随机存取存储器或两者的指令和数据。计算机的基本元件是用于执行指令的处理器以及用于存储指令和数据的一个或多个存储器设备。通常，计算机还将包括或者被操作性地耦合以接收来自用于存储数据的一个或多个大容量存储设备(例如，磁盘、磁光盘或光盘)的数据或者向用于存储数据的一个或多个大容量存储设备传输数据或者两者。然而，计算机不需要具有这种设备。此外，计算机可以嵌入在例如移动电话或其它计算设备的另一设备中。适合用于存储计算机程序指令和数据的计算机可读介质包括所有形式的非易失性存储器、介质和存储器设备，包括(通过示例的方式)半导体存储器设备(例如EPROM、EEPROM和快闪存储器设备)；磁盘(例如，内部硬盘或可移除盘)；磁光盘；以及CDROM和DVD-ROM盘。处理器和存储器可以通过专用逻辑电路来补充或并入在专用逻辑电路中。

为了提供与用户的交互，本说明书中描述的主题的实施例可以实现在具有用于向用户显示信息的显示设备(例如CRT(阴极射线管)或LCD(液晶显示器)监控器))以及用户可以通过其向计算机提供输入的键盘和指向设备(例如，鼠标或轨迹球)的计算机上。其他种类的设备也可以被用来提供与用户的交互；例如，向用户提供的反馈可以是任何适当形式的感觉反馈，例如视觉反馈、听觉反馈或触觉反馈；并且来自用户的输入可以以任何形式被接收，包括声学、语音或触觉输入。

虽然以特定的顺序在附图中描绘了操作，但这不应被理解为要求以所示特定顺序或以连续的顺序执行这些操作，或者所有图示的操作都被执行，以实现期望的结果。在某些环境下，多任务和并行处理可以是有利的。此外，上述实施例中的各个系统部件的分离不应被理解为在所有实施例中都要求这种分离，并且应该理解，所描述的程序部件和系统通常可以在单个软件产品中被集成到一起或者被封装成多个软件产品。

已经描述了若干实施方式。尽管如此，将理解的是，在不脱离本发明的精神和范围的情况下可以做出各种修改。据此，其它实施方式也在权利要求的范围内。