javascript - 泛化 XPath

Question

我想寻求您的帮助以解决我正在尝试解决的涉及 XPath 的问题。

我正在尝试概括用户提供的多个 Xpath，以获得最适合所有提供的示例的 XPath。这是我正在构建的网络抓取系统。

例如:如果用户提供以下 xpath(每个指向 Google 新闻页面“Spotlight”部分中的一个链接)

很好的例子:

/html/body/div[@id='page']/div/div[@id='main-wrapper']/div[@id='main']/div/div/div[3] /div[1]/table[@id='main-am2-pane']/tbody/tr/td[@id='rt-col']/div[3]/div[@id='s_en_us:ir']/div[2]/div[1]/div[2]/a[@id='MAE4AUgAUABgAmoCdXM']/span

/html/body/div[@id='page']/div/div[@id='main-wrapper']/div[@id='main']/div/div/div[3]/div[1]/table[@id='main-am2-pane']/tbody/tr/td[@id='rt-col']/div[3]/div[@id='s_en_us:ir']/div[2]/div[6]/div[2]/a[@id='MAE4AUgFUABgAmoCdXM']/span

/html/body/div[@id='page']/div/div[@id='main-wrapper']/div[@id='main']/div/div/div[3]/div[1]/table[@id='main-am2-pane']/tbody/tr/td[@id='rt-col']/div[3]/div[@id='s_en_us:ir']/div[2]/div[12]/div[2]/a[@id='MAE4AUgLUABgAmoCdXM']/span

错误示例:(指向另一部分中的链接)

/html/body/div[@id='page']/div/div[@id='main-wrapper']/div[@id='main']/div/div/div[3]/div[1]/table[@id='main-am2-pane']/tbody/tr/td[@id='lt-col']/div[2]/div[@id='replaceable-section-blended']/div[1]/div[4]/div/h2/a[@id='MAA4AEgFUABgAWoCdXM']/span

它应该能够概括并生成一个 xpath 表达式，以选择“Spotlight”部分中的所有链接。 (它应该能够抛出给定的不正确的 xpath)

通用 XPath

/html/body/div[@id='page']/div/div[@id='main-wrapper']/div[@id='main']/div/div/div[3]/div[1]/table[@id='main-am2-pane']/tbody/tr/td[@id='rt-col']/div[3]/div[@id='s_en_us:ir']/div[2]/div/div[2]/a[@id='MAE4AUgLUABgAmoCdXM']/span

你能给我建议如何去做吗？我正在考虑使用最长公共(public)子串策略，但是如果给出一个不好的例子(比如给出的第四个例子)，那会过度概括。在这个领域是否有任何库或任何开源软件？

我看到了一些类似的帖子(finding common ancestor from a group of xpath? 和 Howto find the first common XPath ancestor in Javascript?)但是他们在谈论最长的共同祖先。

我正在用 Javascript 编写它作为 firefox 扩展的一种形式。

感谢您的宝贵时间，我们将不胜感激!

Answer 1

这里的问题是自动机最小化问题。所以你有 (Xpath1|Xpath2|Xpath3) 并且你想获得匹配相同节点的最小自动机 Xpath4。还有关于信息丢失或不丢失的最小化问题，如 JPEG。对于精确最小化，您可以在谷歌上搜索“有限状态自动机最小化算法”。

好的，最简单的方法是在将每个 Xpath 运算符转换为字符并从字符串列表运行基于字符的子字符串查找器之后找到公共(public)子序列。所以我们有例如

adcba, acba, adba --common substring--> aba --general reg exp--> a.*b.*a --convert back to xpath--> ...

您也可以尝试设置一些不太通用的东西来代替 .*