Saya memiliki ribuan daftar string, dan setiap daftar memiliki sekitar 10 string. Sebagian besar string dalam daftar yang diberikan sangat mirip, meskipun beberapa string (jarang) sama sekali tidak terkait dengan yang lain dan beberapa string berisi kata-kata yang tidak relevan. Mereka dapat dianggap sebagai variasi berisik dari string kanonik. Saya mencari algoritma atau pustaka yang akan mengubah setiap daftar menjadi string kanonik ini.
Berikut adalah daftar tersebut.
- Star Wars: Episode IV A Harapan Baru | StarWars.com
- Star Wars Episode IV - A New Hope (1977)
- Star Wars: Episode IV - Harapan Baru - Rotten Tomatoes
- Tonton Star Wars: Episode IV - Harapan Baru Online Gratis
- Star Wars (1977) - Film Terbesar
- [REKAM] 4 poster menjanjikan kematian oleh motor tempel - SciFiNow
Untuk daftar ini, string apa pun yang cocok dengan ekspresi reguler ^Star Wars:? Episode IV (- )?A New Hope$akan diterima.
Saya telah melihat kursus Andrew Ng di Machine Learning on Coursera, tetapi saya tidak dapat menemukan masalah yang sama.
nlp
similarity
information-retrieval
lakton
sumber
sumber
Jawaban:
Sebagai solusi naif saya akan menyarankan untuk terlebih dahulu memilih string yang berisi token paling sering di dalam daftar. Dengan cara ini Anda dapat menyingkirkan string yang tidak relevan.
Pada frasa kedua saya akan melakukan voting mayoritas. Dengan asumsi 3 kalimat:
Saya akan memeriksa token satu per satu. Kita mulai dengan "Bintang". Itu menang karena semua string mulai dengan itu. "Perang" juga akan menang. Yang berikutnya adalah ":". Itu juga akan menang.
Semua token akan dapat dalam voting mayoritas sampai "Harapan". Token berikutnya setelah "Harapan" adalah "|", atau "(" atau "-". Tidak ada yang akan menang dalam pemungutan suara mayoritas jadi saya akan berhenti di sini!
Solusi lain mungkin akan menggunakan urutan umum terpanjang .
Seperti yang saya katakan, saya belum banyak memikirkannya. Jadi mungkin ada solusi yang jauh lebih baik untuk masalah Anda :-)
sumber
Pertama hitung jarak sunting antara semua pasangan string. Lihat http://en.wikipedia.org/wiki/Edit_distance dan http://web.stanford.edu/class/cs124/lec/med.pdf . Kemudian kecualikan string outlier apa pun berdasarkan batas jarak tertentu.
Dengan string yang tersisa, Anda dapat menggunakan matriks jarak untuk mengidentifikasi string paling pusat. Bergantung pada metode yang Anda gunakan, Anda mungkin mendapatkan hasil yang ambigu untuk beberapa data. Tidak ada metode yang sempurna untuk semua kemungkinan. Untuk keperluan Anda, yang Anda butuhkan hanyalah beberapa aturan heuristik untuk menyelesaikan ambiguitas - yaitu memilih dua atau lebih kandidat.
Mungkin Anda tidak ingin memilih "paling sentral" dari daftar string Anda, tetapi sebaliknya ingin menghasilkan ekspresi reguler yang menangkap pola umum untuk semua string yang bukan outlier. Salah satu cara untuk melakukan ini adalah mensintesis string yang berjarak sama dari semua string non-outlier. Anda bisa mengetahui jarak sunting yang diperlukan dari matriks, dan kemudian Anda secara acak akan menghasilkan menggunakan jarak tersebut sebagai kendala. Kemudian Anda akan menguji ekspresi reguler kandidat dan menerima yang pertama yang sesuai dengan kendala dan juga menerima semua string dalam daftar non-outlier Anda. (Mulai buat ekspresi reguler dari daftar substring umum terpanjang, karena itu adalah karakter non-wildcard.)
sumber