Mungkinkah komputer "mempelajari" ekspresi reguler dengan contoh yang diberikan pengguna?

Apakah mungkin komputer "mempelajari" ekspresi reguler dengan contoh yang diberikan pengguna?

Untuk memperjelas:

• Saya tidak ingin mempelajari ekspresi reguler.
• Saya ingin membuat program yang "mempelajari" ekspresi reguler dari contoh yang disediakan secara interaktif oleh pengguna, mungkin dengan memilih bagian dari teks atau memilih penanda awal atau akhir.

Apa itu mungkin? Apakah ada algoritme, kata kunci, dll. Yang dapat saya gunakan untuk Google?

EDIT : Terima kasih atas jawabannya, tetapi saya tidak tertarik dengan alat yang menyediakan fitur ini. Saya mencari informasi teoretis, seperti makalah, tutorial, kode sumber, nama algoritme, jadi saya dapat membuat sesuatu untuk diri saya sendiri.

Buku An Introduction to Computational Learning Theory berisi algoritme untuk mempelajari robot terbatas. Karena setiap bahasa reguler setara dengan robot terbatas, dimungkinkan untuk mempelajari beberapa ekspresi reguler oleh sebuah program. Kearns dan Valiant menunjukkan beberapa kasus di mana tidak mungkin mempelajari robot yang terbatas. Masalah terkait adalah mempelajari Model Markov tersembunyi , yang merupakan automata probabilistik yang dapat menggambarkan urutan karakter. Perhatikan bahwa sebagian besar "ekspresi reguler" modern yang digunakan dalam bahasa pemrograman sebenarnya lebih kuat daripada bahasa reguler, dan oleh karena itu terkadang lebih sulit untuk dipelajari.

Ya, bisa saja, kita bisa membuat regex dari contoh (teks -> ekstraksi yang diinginkan). Ini adalah alat online yang berfungsi yang melakukan pekerjaan: http://regex.inginf.units.it/

Alat online Regex Generator ++ menghasilkan regex dari contoh yang diberikan menggunakan algoritme penelusuran GP. Algoritme GP didorong oleh kesesuaian multi-sasaran yang mengarah pada kinerja yang lebih tinggi dan struktur solusi yang lebih sederhana (Occam's Razor). Alat ini adalah aplikasi demostratif oleh Machine Lerning Lab, Universitas Trieste (Università degli studi di Trieste). Silakan lihat tutorial videonya di sini .

Ini adalah proyek penelitian sehingga Anda dapat membaca tentang algoritme yang digunakan di sini .

Melihat! :-)

Menemukan ekspresi reguler / solusi yang bermakna dari contoh adalah mungkin jika dan hanya jika contoh yang diberikan menjelaskan masalah dengan baik. Pertimbangkan contoh-contoh ini yang menjelaskan tugas ekstraksi, kami mencari kode item tertentu; contohnya pasangan teks / ekstraksi:

"The product code is 467-345A" -> "467-345A"
"The item 789-345B is broken"  -> "789-345B"

Seorang pria (manusia), melihat contoh, mungkin berkata: "kode item adalah hal-hal seperti \ d ++ - 345 [AB]"

Ketika kode item lebih permisif tetapi kami belum memberikan contoh lain, kami belum memiliki bukti untuk memahami masalah dengan baik. Saat menerapkan solusi buatan manusia \ d ++ - 345 [AB] ke teks berikut, gagal:

"On the back of the item there is a code: 966-347Z"

Anda harus memberikan contoh lain, untuk lebih menggambarkan apa yang cocok dan apa yang tidak cocok yang diinginkan: - yaitu:

"My phone is +39-128-3905 , and the phone product id is 966-347Z" -> "966-347Z"

Nomor telepon bukanlah id produk, ini mungkin bukti penting.

Tidak ada program komputer yang dapat menghasilkan ekspresi reguler yang bermakna hanya berdasarkan daftar pencocokan yang valid. Biar saya tunjukkan alasannya.

Misalkan Anda memberikan contoh 111111 dan 999999, jika komputer menghasilkan:

1. Ekspresi reguler cocok dengan kedua contoh tersebut: (111111|999999)
2. Ekspresi reguler yang cocok dengan 6 digit identik (\d)\1{5}
3. Sebuah regex yang cocok dengan 6 satu dan sembilan [19]{6}
4. Ekspresi reguler yang cocok dengan 6 digit apa pun \d{6}
5. Salah satu dari tiga di atas, dengan batas kata, mis \b\d{6}\b
6. Salah satu dari tiga yang pertama, tidak diawali atau diikuti dengan digit, mis (?<!\d)\d{6}(?!\d)

Seperti yang Anda lihat, ada banyak cara contoh dapat digeneralisasikan menjadi ekspresi reguler. Satu-satunya cara komputer membuat ekspresi reguler yang dapat diprediksi adalah dengan meminta Anda mencantumkan semua kemungkinan kecocokan. Kemudian itu bisa menghasilkan pola pencarian yang sama persis dengan kecocokan tersebut.

Jika Anda tidak ingin mencantumkan semua kemungkinan kecocokan, Anda memerlukan deskripsi tingkat yang lebih tinggi. Untuk itulah ekspresi reguler dirancang untuk disediakan. Alih-alih memberikan daftar panjang 6 digit angka, Anda cukup memberi tahu program untuk mencocokkan "enam digit". Dalam sintaks ekspresi reguler, ini menjadi \ d {6}.

Metode apa pun untuk memberikan deskripsi tingkat yang lebih tinggi yang sefleksibel ekspresi reguler juga akan serumit ekspresi reguler. Semua alat seperti RegexBuddy dapat melakukannya untuk mempermudah pembuatan dan pengujian deskripsi tingkat tinggi. Alih-alih menggunakan sintaks ekspresi reguler singkat secara langsung, RegexBuddy memungkinkan Anda menggunakan blok penyusun bahasa Inggris biasa. Tetapi itu tidak dapat membuat deskripsi tingkat tinggi untuk Anda, karena ia tidak dapat secara ajaib mengetahui kapan harus menggeneralisasi contoh Anda dan kapan seharusnya tidak.

Sangat mungkin untuk membuat alat yang menggunakan teks contoh bersama dengan pedoman yang diberikan oleh pengguna untuk menghasilkan ekspresi reguler. Bagian tersulit dalam mendesain alat semacam itu adalah bagaimana alat tersebut meminta informasi panduan yang dibutuhkan pengguna, tanpa membuat alat tersebut lebih sulit dipelajari daripada ekspresi reguler itu sendiri, dan tanpa membatasi alat tersebut pada pekerjaan regex umum atau ekspresi reguler sederhana.

Ya, itu pasti "mungkin"; Inilah pseudo-code-nya:

string MakeRegexFromExamples(<listOfPosExamples>, <listOfNegExamples>)
{
   if HasIntersection(<listOfPosExamples>, <listOfNegExamples>)
     return <IntersectionError>

   string regex = "";
   foreach(string example in <listOfPosExamples>)
   {
      if(regex != "")
      {
         regex += "|";
      }
      regex += DoRegexEscaping(example);
   }
   regex = "^(" + regex + ")$";

   // Ignore <listOfNegExamples>; they're excluded by definition

   return regex;
}

Masalahnya adalah jumlah regex yang tidak terbatas akan cocok dengan daftar contoh. Kode ini menyediakan regex paling sederhana / terbodoh di set, pada dasarnya cocok dengan apa pun yang ada di daftar contoh positif (dan tidak ada yang lain, termasuk contoh negatif apa pun).

Saya rasa tantangan sebenarnya adalah menemukan regex terpendek yang cocok dengan semua contoh, tetapi meskipun demikian, pengguna harus memberikan masukan yang sangat baik untuk memastikan ekspresi yang dihasilkan adalah "yang benar".

Saya yakin istilahnya adalah "induksi". Anda ingin membuat tata bahasa yang teratur.

Saya tidak berpikir itu mungkin dengan serangkaian contoh yang terbatas (positif atau negatif). Tapi, jika saya ingat dengan benar, itu bisa dilakukan jika ada Oracle yang bisa dikonsultasikan. (Pada dasarnya Anda harus membiarkan program mengajukan pertanyaan ya / tidak kepada pengguna sampai itu menjadi konten.)

Anda mungkin ingin sedikit bermain-main dengan situs ini, itu cukup keren dan sepertinya itu melakukan sesuatu yang mirip dengan apa yang Anda bicarakan: http://txt2re.com

Ada bahasa yang didedikasikan untuk masalah seperti ini, berdasarkan prolog. Ini disebut progol .

Seperti yang telah disebutkan orang lain, ide dasarnya adalah pembelajaran induktif, sering disebut ILP ( pemrograman logika induktif ) di lingkaran AI.

Tautan kedua adalah artikel wiki di ILP, yang berisi banyak materi sumber berguna jika Anda tertarik untuk mempelajari lebih lanjut tentang topik tersebut.

@Yuval benar. Anda sedang melihat teori pembelajaran komputasi, atau "kesimpulan induktif".

Pertanyaannya lebih rumit dari yang Anda pikirkan, karena definisi "belajar" tidak sepele. Salah satu definisi umum adalah bahwa pelajar dapat melontarkan jawaban kapan pun ia mau, tetapi pada akhirnya, ia harus berhenti mengeluarkan jawaban, atau selalu melontarkan jawaban yang sama. Ini mengasumsikan jumlah masukan yang tidak terbatas, dan sama sekali tidak memberikan jaminan kapan program akan mencapai keputusannya. Selain itu, Anda tidak dapat mengetahui kapan TELAH mencapai keputusannya karena mungkin masih menampilkan sesuatu yang berbeda nanti.

Dengan definisi ini, saya cukup yakin bahwa bahasa biasa dapat dipelajari. Dengan definisi lain, tidak begitu banyak ...

Saya telah melakukan beberapa penelitian di Google dan CiteSeer dan menemukan teknik / makalah berikut:

• Identifikasi bahasa di batas
• Mungkin pembelajaran kira-kira benar

Juga "Belajar set reguler dari pertanyaan dan contoh kontra" Dana Angluin tampaknya menjanjikan, tetapi saya tidak dapat menemukan versi PS atau PDF, hanya kutipan dan makalah seminar.

Tampaknya ini adalah masalah yang rumit bahkan pada tataran teoritis.

Jika memungkinkan bagi seseorang untuk mempelajari ekspresi reguler, maka secara fundamental dimungkinkan untuk sebuah program. Namun, program itu perlu diprogram dengan benar agar dapat belajar. Untungnya ini adalah ruang logika yang cukup terbatas, jadi tidak akan serumit mengajarkan program untuk dapat melihat objek atau sesuatu seperti itu.