algorithm - 从字符串集合中推断模板

Question

我正在为一组网站编制索引，这些网站有大量页面(数千万)，这些页面是从少量模板生成的。我正在寻找一种算法来学习生成页面的模板并将模板与页面匹配，这样我只需要存储可变部分和每个获取页面的模板引用。

该算法不需要产生尽可能大的压缩，但它应该在看到更多页面时变得更好，并且在面对使用以前未见过的模板生成的页面时应该表现得优雅。

我将不胜感激任何对文献或现有图书馆的引用。

我可以对成批页面运行通用压缩算法。我不想这样做的原因是我感兴趣的数据将位于页面的可变部分，因此模板方法允许我在不解压缩的情况下检索它。我希望能够在需要时重新创建整个页面，以确保 future 的可复制性并防止我的抓取程序中出现错误。

Answer 1

在某些圈子里，这个问题被称为“HTML Wrapper Induction”或“Wrapper Learning”。在这篇论文中，您可以找到一个有趣的——尽管是旧的——评论以及一些商业应用程序的链接:http://www.xrce.xerox.com/Research-Development/Historical-projects/IWRAP-Intelligent-Wrapper-Learning-Tools )

您可能对此 Python 库感兴趣:http://code.google.com/p/templatemaker/ “好吧，假设你想从一堆使用相同模板的网页中获取原始数据——例如 Yelp.com 上的餐厅评论。你可以给 templatemaker 任意数量的 HTML 文件，它会创建用于创建这些文件的"template"。” ( http://www.holovaty.com/writing/templatemaker/ )

此外，另一个名为 scrapy 的 Python 库似乎有一个包装归纳库:http://dev.scrapy.org/wiki/Scrapy09Changes#Addedwrapperinductionlibrary

不过，我不能透露太多有关算法的信息。如果您想自己实现一个，这看起来是一个很好的起点:http://portal.acm.org/citation.cfm?id=1859138它同时具有包装器归纳和在线学习功能，因此您可以在继续抓取过程时开始对页面进行分类。