Moin
Ich soll als Hausaufgabe über die Ferien die Frage beantworten, warum eine autonome Schlagwort Extraktion aus Texten (Terminology extraction) NP-Vollständig oder NP-Schwer ist. Der Wikipedia Eintrag hilft mir da leider nicht groß weiter :/ Muss keine Doktorarbeit sein, nur eins zwei Sätze.
Kann mir da vielleicht jemand weiterhelfen?
Viele Grüße,
microkernel
Automatische Schlagwort extraktion aus Texten = NP-Vollständ
- microkernel
- User
- Beiträge: 271
- Registriert: Mittwoch 10. Juni 2009, 17:27
- Wohnort: Frankfurt
- Kontaktdaten:
- cofi
- Python-Forum Veteran
- Beiträge: 4432
- Registriert: Sonntag 30. März 2008, 04:16
- Wohnort: RGFybXN0YWR0
Ich hab keine Ahnung von NLP und kann dir an der Front nicht helfen. Die meist genutzte Technik, um NP-completeness zu zeigen ist wohl die Reduktion auf ein anderes NP-complete Problem.
Wenn der "Beweis" auch sehr informal sein darf, koenntest du zeigen, dass es sehr aufwendig ist (eben O(x^n)) Schlagwoerter zu extrahieren, aber das Bestaetigen von Schlagwoertern aber einfach ist.
Wenn der "Beweis" auch sehr informal sein darf, koenntest du zeigen, dass es sehr aufwendig ist (eben O(x^n)) Schlagwoerter zu extrahieren, aber das Bestaetigen von Schlagwoertern aber einfach ist.
Michael Markert ❖ PEP 8 Übersetzung ❖ Tutorial Übersetzung (3.x) ⇒ Online-Version (Python 3.3) ❖ Deutscher Python-Insider ❖ Projekte
Der Beweis funktioniert besser, wenn man das bereits bekannte NP-vollständige Problem auf das vorhandene reduziertcofi hat geschrieben:Ich hab keine Ahnung von NLP und kann dir an der Front nicht helfen. Die meist genutzte Technik, um NP-completeness zu zeigen ist wohl die Reduktion auf ein anderes NP-complete Problem.
Das Leben ist wie ein Tennisball.