XPaths verallgemeinern

Question

Ich möchte Sie um Hilfe für ein Problem bitten, das ich mit XPaths zu lösen versuche.

Ich versuche, mehrere von einem Benutzer bereitgestellte XPaths zu verallgemeinern, um einen XPath zu erhalten, der am besten zu allen bereitgestellten Beispielen "passt". Dies ist für ein Web-Scraping-System, das ich baue.

Beispiel: Wenn der Nutzer die folgenden xpaths angibt (die jeweils auf einen Link im Abschnitt "Spotlight" auf der Google News-Seite verweisen)

Gute Beispiele:

/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

Schlechte Beispiele: (verweist auf einen Link in einem anderen Abschnitt)

/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

Sie sollte in der Lage sein verallgemeinern und einen xpath-Ausdruck erzeugen die alle Links im Abschnitt 'Spotlight' auswählen würde. (Es sollte in der Lage sein, den angegebenen falschen xpath zu verwerfen)

Verallgemeinerter 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

Könnten Sie mir freundlicherweise einen Rat geben, wie ich vorgehen soll? Ich dachte daran, die Longest Common Substring-Strategie zu verwenden, aber das würde zu sehr verallgemeinern, wenn ein schlechtes Beispiel gegeben wird (wie das vierte Beispiel) Gibt es irgendwelche Bibliotheken oder Open-Source-Software, die in diesem Bereich gemacht wurde?

Ich habe einige ähnliche Beiträge gesehen ( Finden eines gemeinsamen Vorfahren aus einer Gruppe von xpath? y Wie findet man den ersten gemeinsamen XPath-Vorläufer in Javascript? ) Sie sprechen jedoch vom längsten gemeinsamen Vorfahren.

Ich schreibe es in Javascript als eine Art Firefox-Erweiterung.

Vielen Dank für Ihre Zeit und jede Hilfe wäre sehr willkommen!

Answer 1

Die Frage ist hier in Automaton Minimierung Problem. Man hat also (XPfad1|XPfad2|XPfad3) und möchte einen minimalen Automaten XPfad4 erhalten, der denselben Knoten entspricht. Es gibt auch Fragen zur Minimierung mit oder ohne Informationsverlust, wie bei JPEG. Für eine exakte Minimierung können Sie nach "Algorithmen zur Minimierung von endlichen Automaten" googeln.

Ok, der einfachste Weg ist die Suche nach gemeinsamen Teilsequenz, nach der Umwandlung jeder Xpath-Operator zu Zeichen und führen Sie Zeichen-basierte Teilstring-Finder aus Liste der Zeichenfolge. Wir haben also zum Beispiel

adcba, acba, adba --common substring--> aba --general reg exp--> a.*b.*a --zurück zu xpath konvertieren--> ...

Sie können auch versuchen, anstelle von .* etwas weniger Allgemeines anzugeben