用于搜索电子文档中的日期的系统和方法

摘要

一种数据查询系统处理文档中的自由形式文本，以使用扩展的常规表达匹配来识别和定位文档中的一些或者所有日期，从而捕获各种日期格式。该系统封装每个识别的日期的规范化格式，以支持各种类型的查询，例如特定日期查询、分级日期查询、范围日期查询、包括日期和关键字的邻近查询以及查询类型的任何结合。该系统扫描文档以识别在在文档中出现的各种格式日期，消除最终日期出现的歧义，以及根据一种或者多种预定的格式规范化日期。

说明书

技术领域

本发明一般涉及电子文档的文本分析。更具体地，本发明涉及识别电子文档中的日期，其中在所述电子文档中日期以各种格式出现，以及本发明进一步涉及统一地封装所述日期以用于查询目的。

背景技术

理解大的文档集并从中提取有关文档(piece)，搜索日期是有用的基本方面(primitive)。定位万维网上的内容的源日期对于确定与包括日期的搜索请求的相关性是特别有用的。但是，由于在非结构化文本中日期趋向于以各种格式出现，所以有效地执行日期查询是有挑战性的。

例如，日期“2004年10月11日”在文本中可以作为“11^th ofOctober 2004”、“11-10-2004”、“11 October，’04”、“Oct 11^th 04”、“11/10/04”、“10.11.2004”、“2004 Oct 11”等出现。在诸如万维网的多样化集合上，日期表达的变化甚至可以更加显著，其中许多不同的人和组织编写诸如自由形式文本的万维网内容。这是万维网分散化属性以及在自由形式文本上很少强加严格要求的自然结果。

然而，万维网上的自由形式文本是重要的信息源，不管是当前的还是存档的(archived)。报纸和杂志提供了万维网上在线的新的文章；估计万维网上新的源超过了10,000个。这些新的文章涵盖了广泛的话题，迎合了商业和个人的需要。此外，诸如公司和大学的组织公布可以在线获得的丰富的信息。一些搜索引擎站点估计超过80亿索引的网页数目。考虑到万维网上大量源和大量页，对用于搜索和导航这种大集合的自动化技术的需要正在增加。

对于理解在日期附近找到的或者与该日期同一网页上的信息的时间上下文来说，日期是重要的手段。利用具有特定上下文(诸如“在同一页上”、“同一行上”等)的一个或者多个关键字进行查询，例如：

显示涉及特定日期(例如2004年10月11日)的所有页；

显示涉及给定月份(例如2004年10月)中的任何日期的所有页；或者

显示涉及给定年度(例如2004年)中的任何日期的所有页；这些查询都是过滤和导航这种大的网页集的自然并且有用的方法。

虽然传统的万维网搜索引擎使用标准关键字和接近搜索执行得很好，但是希望提出附加的改进。传统的万维网引擎没有充分地通过日期执行搜索。甚至诸如“找到涉及2004年10月11日的所有页”的基本日期查询也要求对于每种可能的日期格式分别进行搜索。因为可能的日期格式的数目是很大的，所以这种搜索是令人生厌并且难以管理的。此外，因为如果日期格式中的数字和句号频繁出现的话，则一些搜索引擎会忽略它们，所以诸如11.10.2004的一些格式是难以搜索的。

对于诸如“找到涉及2004年10月中的任何日期的所有页”的分级(hierarchical)日期查询，使用传统万维网搜索引擎对日期进行搜索会变得更加难以管理。

传统的万维网搜索引擎在搜索含糊(ambiguous)格式的日期时会存在进一步的困难。例如，取决于上下文，11.10.2004可以是指2004年10月11日或者2004年11月10日。当年度被指定为两位数字并且月、日和年在数值上相似时(例如01/04/05)，使含糊性更加复杂。

用于找到源日期的另一种传统方法对于每页找到单个日期，表示何时可能编写了该页，例如页日期。但是，该页日期并不是对所有页都存在。通常没有很好地定义页日期，页日期通常是根据出现在该页上或者在该页的http标题中的不同日期的最好猜测。此外，甚至在页包含附加的日期时，该传统的方法仍然保持每页仅仅一个日期。因此，丢失了关于其它日期的信息，包括用于邻近查询的其它日期的位置。

另一种传统的方法明确地列出了所有可能的备用方案，其中该传统的方法识别命名的实体，例如在文本中可以参考关键字的不同形式。在变量的数量是小数目时，该传统的方法工作得很好。但是，在定位万维网上的源日期的上下文中，对于每个日期的大量可能的格式以及大量可能的不同日期使得该方法很麻烦。因而，对于日期，基于常规表达的识别(spotting)是较好的备用方案。

另一传统的方法包括自然单步常规表达匹配。在特定的上下文中，例如万维网日志(也称作博客(blog))中，该传统的方法在某种程度上基于博客的结构来解决日期的识别。但是，该传统的方法没有针对出现在万维网上的日期的宽范围的可能格式以及识别日期所要求的最终消除歧义(disambiguation)。此外，考虑到大量的可能格式和要求处理的大量页，效率和处理时间对于该传统方法变成了一个严重的问题。

因此，需要一种用于在大的万维网文档集中有效地搜索日期的系统、计算机程序产品以及相关方法。至今仍然没有满足对于这种方案的需要。

发明内容

本发明满足了这个需要，并且提出一种用于在大的万维网文档集中有效地搜索日期的系统、计算机程序产品以及相关方法(在此共同地称为“系统”或者“本发明”)。

本发明的日期匹配模块处理文档中的自由形式文本，以使用扩展的常规表达匹配来识别和定位文档中的一些或者所有日期，从而捕获各种日期格式。本发明的封装模块封装每个识别的日期的规范化格式，以支持各种查询类型，例如特定日期查询、分级日期查询、范围日期查询、邻近日期查询、包括日期和任何关键字的邻近查询，以及查询类型的任意组合。

日期模块扫描文档以得到一些或者所有的日期出现，搜索数字日期和字母形式的月份名。如果找到月份名，前缀模块将前缀常规表达匹配应用到找到的月份名之前的前缀子串，以识别日期的前缀部分，即月份名之前的日期部分。后缀模块将后缀常规表达匹配应用到找到的月份名之后的后缀子串，以识别日期的前缀部分，即月份名之后的日期部分。日期匹配模块通过将前缀部分和后缀部分相关联来确定对应于找到的月份名的日期的一种或者多种格式。日期匹配模块根据找到的月份名、前缀部分和后缀部分来产生选择格式的日期。

本发明的消歧装置消除找到的日期(包括找到的数字日期或者由日期匹配模块产生的日期)出现的歧义。对于具有不容易辨别的日、月或年的日期，希望消除歧义。对于消除歧义的日期出现，规范化装置以一个或者多个规范形式来格式化日期。

附图说明

参考下面的说明、权利要求书和附图，将更详细地说明本发明的各种特征和实现它们的方式，其中在合适时，重复使用参考标记，以表示所参考的项目之间的对应性，并且其中：

图1是其中可以使用本发明的日期搜索系统的示例性操作环境的示意图；

图2是图1的日期搜索系统的高级体系结构的方框图；

图3是描述图1和2的日期搜索系统的操作的方法的处理流程图；

图4包括图4A和图4B，并且表示用于描述图1和2的日期搜索系统的日期匹配模块的操作的方法的处理流程图；以及

图5是对用户提交给包括图1和2的日期搜索系统的搜索引擎的查询的响应的示例性屏幕截取(screen shot)的示意图。

具体实施方式

下面的定义和解释提供了关于本发明的技术领域的背景信息，并且意图在于利于本发明的理解，而不是限制本发明的范围。

自由形式文本：非结构化文本，例如到文字处理器或者文本编辑器的输入，包括例如文字、句子、日期、数字等等。

HTML(超文本标记语言)：用于将呈现和链接属性附着到文档内的信息内容的标准语言。在文档创作阶段，将HTML“标签”嵌入到文档的信息内容内。当万维网服务器发送万维网文档(或者“HTML文档”)到万维网浏览器时，由浏览器解释标签，并且使用来解析和显示文档。除了指定万维网浏览器将如何显示文档外，HTML标签还可以用来创建到其它万维网文档的超链接。

互联网：通过一组标准协议利用路由器链接在一起以形成全球并且分布式网络的互联公共和私人计算机网络的集合。

环球万维网(WWW，也叫万维网)：互联网客户机-服务器超文本分布式信息检索系统。

图1描述了其中可以使用根据本发明的用于有效地在万维网文档集合中搜索日期的系统、服务、计算机程序产品和相关方法(“日期搜索系统10”或者“系统10”)的示例性整体环境。文本分析系统15包括系统10和搜索引擎20。文本分析引擎15分析从诸如WWW的源获得的文档，用于数据分析、趋势发现等等。文本分析引擎包括由搜索引擎20提供的搜索功能。文本分析系统15安装在诸如主服务器25的计算机上。

系统10包括通常嵌入或者安装在主服务器25上的软件编程代码或者计算机程序产品。可替换地，系统10可以被保存在合适的存储介质上，例如磁盘、CD、硬盘驱动器或者类似设备。数据库30(dB30)包括来自诸如WWW的源的文档。虽然将结合WWW说明系统10，但是可以与从WWW或者其它源导出的内容的单独dB 30一起使用系统10。

诸如远程互联网用户的用户由诸如计算机35、40和45的多个计算机来表示，并且可以通过网络50访问主服务器25。计算机35、40和45的每一个包括允许用户与主服务器25安全连接的软件。主服务器25经由诸如电话、电缆或者卫星链路的通信链路55连接到到网络50。计算机35、40和45可以分别经由通信链路60、65和70连接到网络50。虽然相对于网络50说明了系统10，但是计算机35、40和45也可以本地地而不是远程地访问系统10。计算机35、40和45可以通过使用应用手工地或者自动地访问系统10。用户经由网络50和搜索引擎20在dB 30上查询数据。

图2描述了系统10的高级层次结构。系统10包括扩展匹配模块205和封装模块210。扩展匹配模块205包括日期模块215、前缀模块220、后缀模块225、消歧装置230和规范化装置235。

输入240包括没有html标签的文档，诸如来自已经去标签(de-tag)的WWW的任何内容。处理dB 30中的数据，以使用标准的去标签方法移走html标签，以从文档的抓取的(crawled)html内容移走html标签。通过移走交织在日期串中的html标签的复杂性，移走html标签简化了识别日期的处理。移走html标签要求日期出现的跨距和位置的重构；要求跨距和位置，用于包括邻近的查询。由系统10产生的输出245包括每个识别的日期的跨距和位置，用以支持邻近查询。

图3描述了系统10的方法300。扩展匹配模块205处理dB 30中的文档，以识别和定位文档中的一些和所有日期(步骤400，在图4的方法400中进一步描述)。扩展匹配模块205使用扩展的常规表达匹配来捕获各种日期格式。

在自由形式文本中，日期可以以数字或者字母数字的形式出现。字母数字日期以诸如下面的形式出现：

October 11 hh:mm:ss EST 2004

October 11 hh:mm:ss 2004

11 October 2004

October 11 2004

2004 October 11。

在这些示例性字母数字格式的每一个中，在月份的第11日利用上标“th”写为11^th时，产生附加的变量。通常，月份中的日可以被写为1^st、2^nd、3^rd、4^th、5^th等等，或者写为1、2、3、4、5等等。

可以以字母数字形式编写任何日期的可能文本格式的数目是较大的(non-trivial)。日期格式包括年度格式、月份格式、日格式和分隔符格式。

年度的文本表示包括多种年度格式。例如，可以将诸如2004年的年度写为2004、04或者’04。通常，年度可以出现作为完全的四位整数(例如2004)、两位整数(例如04)或者具有前撇号的两位整数(例如’04)。为了消除歧义的目的，系统10使用一个规则，即规定1970年之前的年度利用四位数字完全地规定。系统10将从00到69的两位年度解释为2000到2069。系统10将从70到99的两位年度解释为1970到1999。

月份的文本表示包括多种月份格式。例如，可以以完全形式或者缩写形式(例如对于October作为Oct)进行拼写而编写月份。也可以按照完全形式或者缩写形式，以任何数量的语言来编写月份。可以以大写字母开头、小写字母或者大写字母来编写月份。

此外，日期的非完全指定字母数字格式是常用的。例如，可以将日期表示为月份和年度，而没有随附的日，例如，October 2004或者2004October。可以进一步将日期表示为月份和日，而没有随附的年度，例如October 11^th、11^th October、11 October或者October 11。

此外，诸如间隔、破折号(“-”)、句号(“.”)、逗号(“，”)等的各种特征可以分隔字母数字格式的日期的组成部分。

数字日期包括数字格式，例如

11/10/2004、11-10-2004、11.10.2004，

10/11/2004、10-11-2004、10.11.2004，或者

2004/10/11、2004-10-11、2004.10.11。

可以通过诸如间隔、破折号(“-”)、句号(“.”)、下划线(“_”)、前斜杠(“/”)等的各种特征来分隔字母数字格式的日期的组成部分。在字母数字格式中，年度可以包括两位(例如04)或者四位(例如2004)。

URL串可以包括日期，而在日、月或者年之间没有任何分隔符。在这种情况下，日期可以被编写为数字串，例如对于2004年10月11日来说编写为下列数字串：11102004、10112004或者20041011。

对于以html形式出现的字母数字日期或者数字日期，可以将html标签嵌入到表示日期的串中。例如，串“11^th October 2004”可以被编写为“11^th<b>October</b>2004”，以使月份“October”为粗体字。

图4描述了系统10的扩展匹配模块205的方法400。系统10选择用于处理的文档(步骤405)。日期模块215扫描所选择的文档，以得到数字格式的日期或者包括完全形式或者缩写形式的字母格式的月份名的日期的一次或者多次出现(步骤410)。

扩展匹配模块205确定找到的日期是否包括月份名(确定步骤415)。包括月份名的日期通常包括在月份名之前的字母数字部分(进一步称为前缀部分)以及在月份名之后的字母数字部分(进一步称为后缀部分)。如果找到的日期包括月份名，则前缀模块220将前缀常规表达匹配应用到找到的月份名之前的字符，以识别前缀部分(步骤420)。前缀模块220捕获在长度范围为5个字符到10个字符范围的前缀子串中出现的任何可能的日-年模式。前缀子串的示例性长度为大约10个字符。

后缀模块225将后缀常规表达匹配应用到找到的月份名之后的字符，以识别后缀部分(步骤425)。后缀模块225捕获在长度范围为10个字符到30个字符范围的后缀子串中出现的任何可能的日-年模式。后缀子串的示例性长度为大约20个字符。

通过将前缀部分和后缀部分相关联，扩展匹配模块205确定对于包括月份名的日期的一种或者多种格式(步骤435)。扩展匹配模块205合适地处理任何重叠的日期。例如，串“2003 Oct 11，2004”可以表示“2003 Oct 11”和“Oct 11 2004”。

如果找到的日期包括数字格式(确定步骤425)，则消歧装置230消除每个找到的日期出现的格式的歧义(步骤435)。到消歧装置230的输入包括在步骤410中找到的数字格式的日期或者在步骤430中根据前缀部分、月份名和后缀部分产生的日期。

对于数字日期(例如11.10.2004)和字母数字日期(例如02 October04)会引起歧义，原因在于不大容易辨别日、月或者年。消歧装置230检查日期部分的范围值，以减少歧义。例如，大于12的数字是日或者年，因为每年包括12个月。类似地，大于31的数字是年，因为一个月中日的最大数字为31。

如果必要，消歧装置230使用来自找到所在日期的页的信息来进一步消除日期的歧义。例如，在具有明确日期的页上的另一个日期可以提供日期格式清楚指示。一页可能包括日期9.10.2004；该日期可以是2004年10月9日或者2004年9月10日。通过检查在同一页的其它日期，消歧装置230可以找到日期15.10.2004；该日期只可能是2004年10月15日。因而，在该页的日期格式为dd:mm:yyyy。假设给定页通篇使用同一格式，消歧装置230推知并且推断出当前所选择的日期的格式类似于所选择的页上的其它日期的格式。

消歧装置230应用所希望的附加规则，以进一步消除日期的歧义。消歧装置230根据该页中的连续性来应用这些附加规则。例如在包括08.10.2004、11.10.2004和04.10.2004的页上的日期可能包括格式dd.mm.yyyy。消歧装置230进一步根据与过去/将来相比较的日期来应用附加的规则。例如，如果日期的一种解释是在对于所选择文档驻留的文档集的当前抓取日期之后，则拒绝该解释。消歧装置230根据最新性和靠近性来应用附加的规则。如果可能的日期解释小于抓取日期，则选择更靠近抓取日期的日期解释。例如，在2004年12月抓取的页列出了日期“2004年10月1日”。消歧装置230将日期“01 october 04”解释为2004年10月1日而不是2001年10月4日。

在一个实施例中，消歧装置230使用可利用的站点级信息。消歧装置230从站点的一个或者多个页收集日期格式信息，并且对于日期有歧义的其它页使用所收集的日期信息。

规范化装置235采用由消歧装置230确定的月、日和年，并且以规范形式将日期表示为MMM-dd-yyyy(步骤430)。

封装模块210封装每个识别的日期的规范化格式(步骤304)，以例如支持特定的日期查询、分级日期查询以及范围日期查询。特定的日期查询用来查询对于包括特定日期的文档的内容；示例性特定日期查询是：

“显示涉及特定日期D(例如2004年10月11日)的所有页”。分级日期查询用来查询对于包括月、月和年、或者年的文档的内容；示例性分级日期查询是：

显示涉及给定月份(例如2004年10月)中的任何日期的所有页，或者

显示在给定年度(例如2004)中的任何日期的所有页。

范围日期查询用来查询对于包括日期范围的文档的内容；示例性范围日期查询是：

显示涉及两个日期(例如2004年10月11日和2004年10月22日)之间的任何日期的所有页。

封装模块210按照下面的格式来封装规范化的日期：[[MMM-dd-yyyy]]、[[MMM-yyyy]]、[[yyyy]]以及32位的整数。第一格式[[MMM-dd-yyyy]]帮助执行特定日期查询，第二和第三格式[[MMM-yyyy]]、[[yyyy]]帮助执行分级日期查询，并且第四格式帮助执行日期范围查询。

例如，在特定日期查询中，为了搜索诸如2004年10月11日的日期的所有出现，用户请求[[Oct-11-2004]]。该查询以包括11.10.20004、11-10-04、2004oct.11等的所有格式返回所请求的日期的出现。类似地，在分级日期查询中，为了搜索2004年10月中的所有日期的出现，用户请求[[Oct-2004]]。为了搜索2004年的所有日期，用户请求[[2004]]。

封装模块210进一步封装每个识别的日期的规范化格式(步骤305)，以例如支持包括日期和任何其它关键字的邻近查询。支持邻近查询要求下列知识：日期在文档中的位置、日期的跨距以及与输入240中的一些或者所有文档中的文字相关的跨距。跨距包括在日期或者语句中的令牌的数目的计数。在一个实施例中，由封装模块210产生的日期的规范化格式包括日期在文档中的位置。在另一个实施例中，由封装模块210产生的日期的规范化格式包括日期在文档中的跨距。

封装模块210进一步封装每个识别的日期的规范化格式(步骤305)，以例如支持包括日期和任何其它关键字的邻近查询以及其它任何类型日期查询，例如特定日期查询、分级日期查询和范围日期查询。

系统10支持dB 30的日期查询，使用由封装模块210产生的封装输出查询日期的所有出现(步骤310)。

示例性规范封装包括[[MMM-dd-yyyy]]、[[MMM-yyyy]]、[[yyyy]]以及作为32位的整数。规范化装置235根据规范形式对格式化的日期编索引(index)。例如，规范化装置235给2005年10月11日编索引为Oct-11-2004、Oct-2004和2004。给规范形式的日期编索引允许日期来匹配特定查询和分级查询。使用例如对于年度为11位、对于月份为4位以及对于日为5位，将每个日期转换为整数。将这20位封装为32位整数。

对于每个可能的解释，给不能由消歧装置230解析的日期歧义编索引，这允许歧义日期的任何解释，以匹配相应的用户查询。给歧义日期编索引增加用户的再调用。

图5描述了显示对于“2004年10月中的所有日期”的单个查询的结果的示例性屏幕截取500。屏幕截取500包括菜单条505和一个或多个搜索控制按钮510。在屏幕截取500中列出的是示例性查询响应515、520、525、530、535(被共同称为查询响应540)。通过屏幕截取500中没有示出的查询，可以找到附加的查询响应。

正如查询响应540中所看到的，系统10识别各种形式的日期，并且封装这些日期，使得通过简单的查询就可以找到这些日期。示例性查询响应515包括显示为2004年10月19日的日期。示例性查询响应520包括显示为2004年10月26日的日期。示例性查询响应3包括显示为2004年10月14日的日期。示例性查询响应5包括显示为10.14.2004的日期。在查询响应540中的每个日期的月份被以某种形式强调，例如粗体、斜体、下划线(正如所示)等等。

应当理解，所说明的本发明的特定实施例只是本发明原理的某些应用的描述。在没有偏离本发明精神和范围的情况下，可以对在此说明的用于在万维网文档集中有效地搜索日期的系统和方法做出许多修改。