1958年11月,在一个为期六天的科学信息国际会议上,发明家汉斯·彼得·卢恩展示了他的一系列机电机器。他们看起来相当普通。就像当时的其他计算设备一样,它们四四方方、实用,用来将成堆的穿孔卡舀进插槽和箱子里。
然而,与其他计算机不同的是,卢恩的设备不是用来处理数字和计算的,而是用来处理单词和句子的。其中一台机器特别引人注目,它实现了一种被卢恩称为算法的算法KWIC,即语境中的关键字.KWIC系统接收大量文本(通常是长度在500到5000字之间的文章)可以快速自动地构建一种索引。
当时,索引、分类和组织书面信息是一个艰苦的过程,即使对最有经验的专家也是如此。许多领域的信息量增长太快,任何人都无法跟上。人们迫切需要一种更好的抽象和总结的方法。对于在华盛顿特区举行的图书馆员和信息科学家的聚会来说,KWIC的展示简直是惊天动地,美国各地的报纸都报道了卢恩令人震惊的发明。
到20世纪60年代初,KWIC已经成为数百个计算机化索引系统设计的核心,包括化学文摘服务、生物文摘和科学信息研究所使用的系统。一位专家称KWIC是“自试管发明以来化学领域发生的最伟大的事情”。Luhn是IBM的高级工程师,他还将KWIC构建为企业的“情报系统”,旨在识别并将相关信息传递给大型组织中的特定个人。KWIC基本上相当于那个时代的搜索引擎:它允许用户快速找到他们需要的信息。
我们现在理所当然地认为计算机可以理解信息,随时提供餐馆评论、体育比分和股票价格。然而,在卢恩的时代,计算机是粗糙而简单的。他对文本操作的尝试使人们对计算机及其功能有了更广阔的思考方式,他的思想仍然支撑着我们用于在线购物、自动翻译和基因研究的现代算法。当然,在20世纪50年代,许多这样的应用甚至是不可想象的。在这里,我将探索是什么导致Luhn解决了一个当时还不存在的问题——一个叫做哈希函数的解决方案。
二战后的几年是电子计算机的雏形。战争期间制造的各种计算机对弹道、原子武器和密码学进行了至关重要的计算。冷战的紧张局势确保了对计算机发展的持续资助,其结果是计算机发展得更快、更准确、更强大。但它们的主要用途——处理和存储数字——变化不大。
在这个新生的计算机世界里,卢恩是一个不同寻常的人物。卢恩一生都穿着优雅,1941年来到IBM时,他对纺织业的了解超过了计算机科学。他的许多发明似乎都属于机械计算器和计算尺的前数字时代。甚至在20世纪50年代,数字计算机就已经取代了他的机电设备。尽管如此,他的想法经过各种目的的转换和重新组合,现在几乎嵌入到我们能想到的所有软件中。
1896年,卢恩出生在德国巴门。他的父亲约翰(Johann)是一位印刷大师,家境富裕,显然对孩子们的努力非常宽容。有一次,卢恩和他的弟弟妹妹们在家里的花园里建造了一条微型铁路,其中包括用熔化印刷铅制成的70米长的轨道。
高中毕业后,卢恩去瑞士学习家族生意。但第一次世界大战和在德国军队的短暂服役中断了他的印刷生涯,战争结束后,他开始从事纺织品贸易。1924年,卢恩来到美国,寻找纺织厂的潜在地点。即使在纺织业,卢恩的发明倾向也很明显。1927年,他发明了一种类似尺子的装置,可以用来测量布的线数。的Lunometer目前仍由卢恩创立的工程咨询公司H.P. Luhn & Associates出售。
卢恩学习很快,从各种各样的领域吸收信息,进而成为一名熟练的登山者、美食厨师和专业的风景画家。在20世纪30年代,他的众多专利包括一项可折叠的雨衣这是一种塑形女性长筒袜的设备,游戏桌,以及“鸡尾酒甲骨文——这是一个指南,告诉用户可以用手头的原料制作什么饮料。
饮料,有人知道吗?卢恩的发明创造思想到处都是。1933年,禁酒令结束前不久,他为一份配方指南申请了美国专利,该指南可以帮助用户从手边的材料中制作鸡尾酒。插图:美国专利和商标局
但卢恩真正感兴趣的是信息的存储、通信和检索,尤其是文本,他加入IBM主要是为了追求这些兴趣。尽管拥有“发明家”的头衔,但卢恩的成果却非常丰富——他最终为IBM创造了70项专利。尽管他可以解决任何他喜欢的问题,但他的许多发明都集中在使用机器,包括电子计算机,来处理信息。
例如,在1946年和1947年,卢恩致力于创建机器可读的打印文件。其中一种设备是将金属带插入打字机,然后将磁性图案打到纸上,然后由机器扫描。不久之后,他开始与麻省理工学院的两位化学家马尔科姆·戴森(Malcolm Dyson)和詹姆斯·佩里(James Perry)合作,研制一种可以使用打孔卡自动搜索化合物的机器。每个穿孔卡都被编码了关于特定化合物的信息。用户在机器中插入一张“问题卡”,上面列出了一组标准,所有的复合卡都可以根据这些标准进行比较和排序。虽然卢恩的扫描仪是高度专业化的,但他继续寻找更通用的自动处理信息的方法。
人们脑子里有很多信息。战后,科学和工程领域发表的论文数量呈爆炸式增长。许多专家担心,“信息过载”可能会使研究人员和商人不堪重负。Vannevar Bush他是美国战时庞大科学官僚机构的领导人,也是美国国家科学基金会的设计师之一,他提出了一种办公桌大小的机电设备,麦麦克斯,用于存储和连接信息。
布什的想法从未实现,但卢恩的想法实现了。例如,1954年1月6日,他申请了一项美国专利。数字验证计算机”[PDF]。这种手持机械装置旨在解决一个简单的实际问题。当时,各种身份识别号码,如信用卡号码和社会安全号码,开始在公共和私人生活中发挥重要作用。但这些数字很难记住,它们可能被错误地转录或故意伪造。所需要的是一种快速验证身份证号码是否有效的方法。
卢恩的掌上电脑利用他开发的校验和算法做到了这一点。对于一个10位数的数字,计算机将执行以下步骤:
- 每两位数加倍
- 如果任何结果大于或等于10,将该结果的数字相加得到一个个位数(例如,“16”将变成1 + 6 = 7)。
- 将新号码的10位数字全部相加
- 乘以9
- 取结果的最后一位
这个方法产生了一个个位数的“检查”数字。在Luhn最初的公式中,0表示原始数字是有效的。在后来的版本中,支票只是作为最后一个数字附加到原始数字之后,这样您就可以很容易地验证最后一个数字是否与他的机器生成的支票号码相匹配。底层的计算序列,现在被称为模数10算法,仍然被广泛使用。分配给移动电话的IMEI (International Mobile Equipment Identity)号码就是通过这种方式验证的。
更重要的是,卢恩机器的齿轮和轮子成为了数字时代最重要的算法之一:哈希的基础。这类广泛的算法提供了一种强大的组织信息的方法,这样计算机就很容易找到信息。就像腌牛肉和土豆的烹饪哈希一样,哈希算法以各种方式切割和混合数据。这种混合,如果巧妙地部署,可以加快许多类型的计算机操作。
1953年初,卢恩写了一份IBM内部备忘录,建议将信息放入“桶”中,以加快搜索速度。假设您想在数据库中查找一个电话号码,并找出它属于谁。给定10位数字314-159-2652,计算机只需在列表中一次搜索一个数字,直到找到相关条目。然而,在一个包含数百万个数字的数据库中,这可能需要一段时间。
Luhn的想法是将每个条目分配到一个编号桶中,如下所示:电话号码的数字被分组成一对(在本例中为31、41、59、26、52)。然后将配对的数字相加(4,5,14,8,7),由此生成一个新的数字,由每个个位数结果组成,如果是两位数结果,则只包括最后一位(产生45487)。原始电话号码和对应的名称或地址将被放入一个标记为45487的bucket中。
从电话号码中查找条目需要使用Luhn的方法快速计算桶号,然后从该桶中检索信息。即使每个bucket包含多个条目,按顺序搜索单个bucket也比搜索整个列表快得多。
几十年来,计算机科学家和程序员对卢恩的方法进行了改进,并将其推向了新的用途。但基本的思想还是一样的:用一个数学问题将数据组织成易于搜索的桶。由于组织和搜索数据在计算中是如此普遍的问题,哈希算法已经成为密码学、图形学、电信和生物学的关键。每次通过Web发送信用卡号码或使用文字处理程序的字典时,哈希函数都在工作。
快速索引:在1958年的国际科学信息会议上,Hans Peter Luhn(右)展示了IBM自动生成文档索引的系统,该系统基于他开发的一种名为KWIC(上下文关键字)的算法。照片:IBM
卢恩关于计算的想法远远超出了简单的查找。他认为计算机可以成为复杂的文本操纵者——用于阅读和理解书面语言,然后对这些信息进行索引和组织,从而解决科学和商业中的实际问题。到1958年,他的化学卡片分拣机已经发展成为通用卡片扫描仪和9900特殊索引分析仪,他在华盛顿特区的会议上演示了这些。这些是机电设备,可以根据用户的标准搜索和分类穿孔卡片。
然而,真正引起轰动的是KWIC,即卢恩的计算机化编制索引的方法。索引是一本书或文集中使用的关键词按字母顺序排列的列表。它就像一个索引,但它只列出了文本中出现的实际单词,而不是概念(而且它排除了琐碎的单词,比如一个而且的).长期以来,神学和语言学一直使用索引。例如,圣经的索引会显示这个词的每一个实例爱,引用书,章节和诗句。在全文计算机搜索出现之前,建立一个索引是很困难的,通常只对像《圣经》或莎士比亚文集这样的重要作品进行检索。
就像卢恩的桶形格式适用于数字一样,他的KWIC索引系统适用于文本。两者都使大量信息易于搜索。举一个非常简单的例子,假设你想要生成以下四本书标题中的单词的一致性:乱世佳人,战争与和平,风的影子,战争阴影.
这些标题的KWIC索引将产生
走了 | 随风而来 | |
战争和 | 和平 | |
的 | 影子 | 风的故事 |
阴影 | 战争的 | |
战争 | 与和平 | |
的影子 | 战争 | |
一去不复返 | 风 | |
The Shadow of The | 风 |
KWIC算法将标题中的单词按所有可能的顺序重新排列,然后按字母顺序排列。结果是一个完整的关键词列表(意思是除了介词、连词和冠词之外的所有东西)。
卢恩的KWIC系统很快被整个科学界所采用。他知道这对商业用户也很有用。1958年,他写了一篇文章IBM研究与开发杂志标题为“商业智能系统”。在这篇文章中,他提出了一个系统,可以自动生成文章摘要,从摘要中提取“行动点”,然后将结果分发给组织内合适的人员。卢恩明白,要解决信息过载的问题,就必须想出一种方法,在不给人们带来无关材料负担的情况下,快速地从海量信息中进行分类。
《纽约时报》,在卢恩1964年的讣告中他这样描述他的自动抽象系统:
在一次演示中,卢恩把一篇2326字的关于神经系统激素的文章从科学美国人他把它以磁带的形式插入ibm电脑,然后按下一个按钮。三分钟后,这台机器的自动打字机打出了四句话,给出了这篇文章的要点,机器对这些要点做了一个摘要。
Luhn的抽象程序首先计算一篇文章中所有单词的出现频率。在丢弃了非常常见的单词后,自动抽象机定位了几个最常见的单词同时出现的句子。这样的句子被认为是整体内容的代表,因此被放在摘要中。这是一种纯粹的统计方法,并没有试图“理解”一篇文章中的词语或它们之间的关系。但就像KWIC一样,它展示了计算机如何有效地将文本组织成人类更容易理解的格式。
1961年,卢恩从IBM退休三年后死于白血病,他没能活着看到互联网和网络带来的深刻变化。除了有限的信息专家、纺织品制造商和历史学家之外,他的名字基本上被遗忘了。但卢恩的思想经久不衰。今天,哈希在管理和保护我们的数字生活中扮演着许多角色。当你在网站上输入密码时,服务器可能会存储你密码的散列版本。当你使用安全连接(URL以“https”开头)与网站交互或用比特币购买东西时,哈希也在那里发挥作用。对于Dropbox和谷歌Drive这样的云服务,哈希使存储和共享文件的效率大大提高。在遗传学和其他数据密集型研究中,哈希极大地减少了计算筛选大量数据所需的时间。
哈希已经把计算机变成了文本工具,可以用字母和单词进行推理。谷歌翻译,谷歌N-gram,谷歌AdWords和谷歌搜索都致力于以某种方式确定文本的含义。网络上信息的爆炸使得自动化阅读和理解对商业、科学和每个人都至关重要。哈希的发展与文本有关,反映在Luhn对单词、句子、索引、摘要、索引和摘要的思考中。
这就是卢恩的遗产:他帮助证明了计算机和计算不仅仅是数学、统计学和逻辑学的领域,也是语言、语言学和文学的领域。在他的时代,这是一种革命性的思考机器的方式。
技术历史学家Michael Mahoney他称计算机为“千变万化的机器”:不只是一种东西,而是许多东西,一台等待被塑造成不同用途的机器。即使是现在,我们也倾向于以一种狭隘的方式来看待计算机,就像巨大的数字处理器,每秒执行如此多的计算和操作。汉斯·彼得·卢恩对计算机的看法更有远见。通过想象计算机的多样性,他帮助开辟了有希望的探索新领域。
作者简介
哈勒姆史蒂文斯他是新加坡南洋理工大学的历史学教授。