Metode sederhana untuk mendeteksi kode dalam teks secara andal?

GMail memiliki fitur ini di mana ia akan memperingatkan Anda jika Anda mencoba mengirim email yang menurutnya mungkin memiliki lampiran.

Karena GMail mendeteksi string see the attacheddalam email, tetapi tidak ada lampiran yang sebenarnya, itu memperingatkan saya dengan dialog OK / Batalkan ketika saya mengklik tombol Kirim.

Kami memiliki masalah terkait pada Stack Overflow. Yaitu, ketika pengguna memasukkan posting seperti ini :

masalah saya adalah saya perlu mengubah database tetapi saya tidak akan membuat 
koneksi baru. contoh:

DataSet dsMasterInfo = DataSet baru ();
Database db = DatabaseFactory.CreateDatabase ("ConnectionString");
DbCommand dbCommand = db.GetStoredProcCommand ("uspGetMasterName");

Pengguna ini tidak memformat kode mereka sebagai kode!

Artinya, mereka tidak membuat indentasi dengan 4 spasi per penurunan harga, atau menggunakan tombol kode (atau pintasan keyboard ctrl+ k) yang melakukan itu untuk mereka.

Dengan demikian, sistem kami menerima banyak pengeditan di mana orang harus masuk dan memformat kode secara manual untuk orang yang entah bagaimana tidak dapat mengetahui hal ini. Ini mengarah ke banyak bellyaching . Kami telah meningkatkan bantuan editor beberapa kali, tetapi tidak sampai ke rumah pengguna dan menekan tombol yang benar pada keyboard mereka untuk mereka, kami bingung untuk melihat apa yang harus dilakukan selanjutnya.

Itu sebabnya kami mempertimbangkan peringatan gaya GMail Google:

Apakah Anda bermaksud memposting kode?

Anda menulis hal-hal yang kami anggap mirip kode, tetapi Anda tidak memformatnya sebagai kode dengan indentasi 4 spasi, menggunakan tombol kode bilah alat atau perintah pemformatan ctrl+ kkode.

Namun, menghadirkan peringatan ini mengharuskan kita untuk mendeteksi keberadaan kode yang kita pikir tidak terformat dalam sebuah pertanyaan . Apa cara sederhana, semi-andal dalam melakukan ini?

• Per penurunan harga , kode selalu diindentasi oleh 4 spasi atau dalam backtick, sehingga apapun yang diformat dengan benar dapat dibuang dari cek dengan segera.
• Ini hanya peringatan dan itu hanya akan berlaku untuk pengguna dengan reputasi rendah yang menanyakan pertanyaan pertama mereka (atau memberikan jawaban pertama mereka), sehingga beberapa positif palsu tidak apa-apa, selama mereka sekitar 5% atau kurang.
• Pertanyaan tentang Stack Overflow dapat dalam bahasa apa pun , meskipun secara realistis kami dapat membatasi pemeriksaan kami untuk, katakanlah, bahasa "sepuluh besar". Per halaman tag yang akan menjadi C #, Java, PHP, JavaScript, Objective-C, C, C ++, Python, Ruby.
• Gunakan dump data kreatif Commons Stack Overflow untuk mengaudit solusi potensial Anda (atau hanya mengambil beberapa pertanyaan di 10 tag teratas pada Stack Overflow) dan lihat bagaimana hasilnya.
• Pseudocode baik-baik saja, tetapi kami menggunakan c # jika Anda ingin lebih ramah.
• Semakin sederhana semakin baik (asalkan bekerja). CIUMAN! Jika solusi Anda mengharuskan kami untuk mencoba mengompilasi pos dalam 10 penyusun yang berbeda, atau pasukan orang untuk melatih mesin inferensi bayesian secara manual, itu ... tidak persis seperti yang kami pikirkan.

Solusi yang tepat mungkin adalah model pembelajaran / statistik, tetapi berikut adalah beberapa ide yang menyenangkan:

1. Semi-titik dua di akhir baris . Ini saja akan menangkap sejumlah besar bahasa.
2. Kurung langsung mengikuti teks tanpa ruang untuk memisahkannya: myFunc()
3. Titik atau panah di antara dua kata: foo.bar = ptr->val
4. Adanya kurung kurawal, kurung: while (true) { bar[i]; }
5. Kehadiran sintaks "komentar" (/ *, //, dll): /* multi-line comment */
6. Karakter / operator yang tidak umum: +, *, &, &&, |, ||, <, >, ==, !=, >=, <=, >>, <<, ::, __
7. Jalankan highlighter sintaks Anda pada teks. Jika akhirnya menyoroti beberapa persentase tinggi, itu mungkin kode.
8. teks camelCase dalam posting.
9. kurung bersarang, kawat gigi, dan / atau kurung.

Seseorang dapat melacak berapa kali masing-masing ini muncul, dan ini dapat digunakan sebagai fitur dalam algoritma pembelajaran mesin seperti perceptron , seperti yang dilakukan SpamAssassin.

Saya akan penasaran untuk melihat apa metrik rata-rata bahasa Inggris tertulis di satu sisi, dan kode di sisi lain.

• panjang paragraf
• panjang garis
• ukuran kata
• karakter yang digunakan
• rasio antara karakter alfabet, numerik dan simbol lainnya
• jumlah simbol per kata
• dll.

Mungkin itu saja sudah bisa membedakan antara kode dan sisanya. Setidaknya saya percaya kode, terlepas dari bahasa, akan menunjukkan beberapa metrik yang sangat berbeda dalam banyak kasus.

Berita baiknya adalah: Anda sudah memiliki banyak data untuk membangun statistik Anda.

Ok saya kembali dengan beberapa data untuk mendukung asumsi saya. :-)

Saya melakukan tes cepat dan kotor pada posting Anda sendiri dan di posting pertama saya temukan di StackOverflow , dengan alat yang cukup canggih: wc.

Inilah yang saya miliki setelah menjalankan wcpada bagian teks dan pada bagian kode dari dua contoh:

Pertama mari kita lihat bagian bahasa Inggris :

• Bagian bahasa Inggris dari pos Anda (2635 karakter, 468 kata, 32 baris)
  • 5 karakter / kata, 82 karakter / baris, 14 kata / baris
• Bagian bahasa Inggris dari pos lainnya (1499 karakter, 237 kata, 12 baris)
  • 6 karakter / kata, 124 karakter / baris, 19 kata / baris

Cukup mirip bukan?

Sekarang mari kita lihat bagian kode !

• Bagian kode dari pos Anda (174 karakter, 13 kata, 3 baris)
  • 13 karakter / kata, 58 karakter / baris, 4 kata / baris
• Bagian kode dari pos lain (4181 karakter, 287 kata, 151 baris)
  • 14 karakter / kata, 27 karakter / baris, 2 kata / baris

Lihat betapa tidak terlalu berbedanya metrik-metrik itu, tetapi yang lebih penting, betapa berbedanya mereka dari metrik bahasa Inggris? Dan ini hanya menggunakan alat terbatas. Saya sekarang yakin Anda bisa mendapatkan sesuatu yang benar-benar akurat dengan mengukur lebih banyak metrik (saya sedang memikirkan statistik chars).

Saya dapat membuat cookie?

Biasanya, rantai Markov digunakan untuk menghasilkan teks, tetapi mereka juga dapat digunakan untuk memprediksi kesamaan teks (per CE Shannon 1950 ) dengan model yang terlatih. Saya merekomendasikan beberapa rantai Markov.

Untuk setiap bahasa yang lazim, latih rantai Markov pada sampel kode yang besar dan representatif dalam bahasa tersebut. Kemudian, untuk posting Stack Overflow yang ingin Anda deteksi kode, lakukan hal berikut untuk setiap rantai:

• Ulangi garis-garis di pos.
  • Nyatakan dua variabel: ACTUAL = 1.0 dan TERTINGGI = 1.0
  • Ulangi setiap karakter dalam barisan.
    • Untuk setiap karakter, temukan probabilitas dalam rantai Markov bahwa karakter saat ini adalah yang mengikuti karakter N sebelumnya. Set AKTUAL = AKTUAL * MASALAH ₁ . Jika karakter saat ini tidak ada dalam rantai, maka gunakan nilai kecil untuk PROB ₁ , seperti 0,000001.
    • Sekarang, cari karakter yang paling mungkin (yaitu probabilitas tertinggi) untuk mengikuti karakter N sebelumnya. Tetapkan TERTINGGI = TERTINGGI * MASALAH ₂ .
    • Jelas, PROB ₂ > = PROB ₁

Untuk setiap baris, Anda harus memiliki nilai AKTUAL dan TERTINGGI. Bagilah AKTUAL dengan TERTINGGI. Itu akan memberi Anda skor kebugaran, apakah baris tertentu adalah kode sumber. Itu akan mengaitkan angka dengan masing-masing baris dalam contoh yang Anda berikan:

my problem is I need to change the database but I don't won't to create // 0.0032
a new connection. example: // 0.0023

DataSet dsMasterInfo = new DataSet(); // 0.04
Database db = DatabaseFactory.CreateDatabase("ConnectionString");   // 0.05
DbCommand dbCommand = db.GetStoredProcCommand("uspGetMasterName");  // 0.04

Terakhir, Anda harus memilih ambang untuk menentukan kapan ada kode di pos. Ini bisa menjadi angka yang dipilih oleh pengamatan yang menghasilkan kinerja tinggi. Bisa juga memperhitungkan jumlah garis dengan skor tinggi.

Latihan

Untuk melatih, sediakan contoh kode yang besar dan representatif dalam bahasa tersebut. Tulis sebuah program untuk mengulang teks kode dan kaitkan setiap N-gram dalam file (kisaran untuk N harus diparameterisasi) dengan frekuensi statistik dari karakter berikutnya. Ini akan menghasilkan beberapa kemungkinan status karakter yang mengikuti bigram, masing-masing terkait dengan probabilitas. Misalnya, bigram "()" dapat memiliki beberapa probabilitas karakter berikut:

"()" 0.5-> ";"
"()" 0.2-> "."
"()" 0.3-> "{"

Yang pertama harus dibaca, misalnya sebagai "Probabilitas bahwa tanda titik koma mengikuti tanda kurung kosong adalah 0,5."

Untuk pelatihan, saya merekomendasikan N-gram ukuran dua hingga lima. Kembali ketika saya melakukan riset tentang ini , kami menemukan bahwa N-gram ukuran dua hingga lima bekerja dengan baik untuk bahasa Inggris. Karena banyak kode sumber seperti bahasa Inggris, saya sarankan mulai dengan rentang itu dan kemudian menyesuaikan untuk menemukan nilai parameter optimal saat Anda menemukan yang berfungsi.

Peringatan: Model ini akan dipengaruhi oleh pengidentifikasi, nama metode, spasi, dan lain-lain. Namun, Anda dapat menyesuaikan pelatihan untuk menghilangkan fitur tertentu dari sampel pelatihan. Misalnya, Anda bisa menutup semua spasi putih yang tidak perlu. Kehadiran spasi putih di input (pos Stack Overflow) dapat diabaikan juga. Anda juga bisa mengabaikan huruf abjad, yang akan lebih tangguh dalam menghadapi berbagai konvensi penamaan pengidentifikasi.

Selama penelitian saya , kami menemukan bahwa metode kami bekerja dengan baik untuk bahasa Spanyol dan juga bahasa Inggris. Saya tidak melihat mengapa ini juga tidak berfungsi dengan baik untuk kode sumber. Kode sumber bahkan lebih terstruktur dan dapat diprediksi daripada bahasa manusia.

Bolehkah saya menyarankan pendekatan yang sangat berbeda? Di SO, satu-satunya bahasa manusia yang diizinkan adalah bahasa Inggris, jadi apa pun yang bukan bahasa Inggris memiliki 99,9% peluang untuk menjadi cuplikan kode .

Jadi solusi saya adalah: gunakan salah satu dari banyak checker bahasa Inggris di luar sana (pastikan mereka juga memberi sinyal - di samping salah eja - kesalahan sintaksis seperti titik ganda, atau simbol non-bahasa seperti #atau ~). Maka setiap baris / paragraf yang melempar sejumlah besar kesalahan dan peringatan akan memicu "apakah kode ini?" pertanyaan.

Pendekatan ini juga dapat disesuaikan untuk situs-situs StackExchange menggunakan bahasa lain selain bahasa Inggris, tentu saja.

Hanya 2 ¢ saya ...

Saya mungkin akan mendapatkan beberapa suara untuk ini, tetapi saya pikir Anda mendekati ini dari sudut yang salah.

Baris ini membuat saya:

orang harus masuk dan memformat kode secara manual untuk orang yang entah bagaimana tidak dapat mengetahui hal ini

IMO bahwa sudut pandangnya agak sombong. Saya menemukan ini banyak dalam desain perangkat lunak di mana programmer dan desainer merasa jengkel dengan pengguna yang tidak tahu cara menggunakan perangkat lunak dengan benar, ketika masalahnya bukan pengguna tetapi perangkat lunak itu sendiri - atau setidaknya UI.

Penyebab utama masalah ini bukan pengguna tetapi fakta bahwa tidak jelas bagi mereka bahwa mereka dapat melakukan ini.

Bagaimana dengan perubahan di UI untuk membuat ini lebih jelas? Tentunya ini akan menjadi:

1. lebih jelas bagi pengguna baru persis apa yang harus mereka lakukan
2. lebih mudah bagi Anda untuk membangun daripada menulis algoritma yang kompleks untuk mendeteksi logika kode dari banyak bahasa

Contoh:

Kode pseudo akan menimbulkan tantangan nyata karena semua bahasa pemrograman bergantung pada karakter khusus seperti '[]', ';', '('), dll. Cukup hitung kemunculan karakter khusus ini. Sama seperti Anda akan mendeteksi file biner (lebih dari 5% sampel berisi nilai byte 0).

Saya pikir Anda mungkin perlu menargetkan ini hanya terhadap bahasa tertentu, secara umum masalah ini kemungkinan tidak dapat diselesaikan karena Anda bisa mendapatkan bahasa yang sangat mirip dengan bahasa Inggris (mis. Inform7 ). tapi untungnya yang paling sering digunakan bisa ditutupi dengan cukup mudah.

Pemotongan pertama saya adalah mencari urutan "; \ n" yang akan membuat Anda cocok untuk C, C ++, Java, C # dan bahasa lain yang menggunakan sintaksis yang sama dan sangat sederhana. Ini juga cenderung digunakan dalam bahasa Inggris daripada a; tanpa baris baru

Seseorang menyebutkan melihat tag dan kemudian mencari sintaks untuk itu tetapi itu ditembak karena ini ditujukan untuk pengguna baru.

Solusi yang mungkin lebih baik adalah mencari nama bahasa di tubuh pertanyaan, kemudian menerapkan strategi yang sama. Jika saya menyebutkan "Javascript", "Java" atau "C #" maka kemungkinannya adalah itulah pertanyaannya, dan kode dalam pertanyaan tersebut cenderung dalam bahasa itu.

Pertama, jalankan melalui pemeriksa ejaan, ia akan menemukan sangat sedikit kata-kata bahasa Inggris yang tepat, namun harus ada banyak kata yang disarankan oleh pemeriksa ejaan untuk dipisah.

Lalu ada tanda baca / karakter khusus yang tidak biasa untuk bahasa Inggris biasa, khas untuk kode:

• something(); tidak bisa hanya bahasa Inggris biasa;
• $somethingdi mana somethingtidak semua numerik;
• -> antara kata tanpa spasi;
• . antara kata tanpa ruang;

Tentu saja untuk membuatnya bekerja dengan baik, Anda mungkin ingin agar classifier Bayesian dibangun di atas karakteristik ini.

ada beberapa set bahasa yang memiliki sintaksis yang sama. sebagian besar bahasa dipengaruhi oleh beberapa bahasa, sehingga bahasa [AMPL, AWK, csh, C ++, C--, C #, Objective-C, BitC, D, Go, Java, JavaScript, Limbo, LPC, Perl, PHP, Pike, Processing [semuanya dipengaruhi oleh C, jadi jika Anda mendeteksi C Anda mungkin akan mendeteksi semua bahasa ini. jadi Anda hanya perlu menulis pola sederhana untuk mendeteksi set bahasa ini.

saya juga akan membagi teks menjadi blok karena sebagian besar kode akan dibagi oleh dua baris baru atau serupa dari blok teks lain dalam posting.

ini bisa dengan mudah dilakukan dengan javascript (sampel super lengkap untuk keluarga c):

var txt = "my problem is I need to change the database but I don't won't to create a new connection. example:\n\nDataSet dsMasterInfo = new DataSet();Database db = DatabaseFactory.CreateDatabase("ConnectionString");DbCommand dbCommand = db.GetStoredProcCommand("uspGetMasterName");";
var blocks = txt.split(/\n\n/gi); console.dir(blocks);
var i = blocks.length;
var cReg = /if\s*\(.+?\)|.*(?:int|char|string|short|long).*?=.+|while\s*\(.+?\)/gi;

while ( i-- ){
   var current = blocks[i];
   if ( cReg.test( current ) ){
      console.log("found code in block[" +  i + "]");
   }
}

Cukup hitung kata-kata / karakter tanda baca untuk setiap baris. Bahasa Inggris akan cenderung memiliki 4 atau lebih, kode kurang dari 2.

Paragraf di atas memiliki 18 kata, dan 4 karakter tanda baca, misalnya. Paragraf ini memiliki 19 kata dan 4 tanda baca, sehingga sesuai harapan.

Tentu saja, ini perlu diuji terhadap pertanyaan-pertanyaan penutur pemula berbahasa Inggris yang kurang baik, dan mungkin dalam kasus-kasus itu, statistik cenderung miring.

Saya berharap [non-spasi putih]. [Spasi putih atau baris baru] sangat jarang dalam kode, tetapi umum dalam bahasa Inggris, jadi ini bisa dihitung sebagai kata-kata, bukan tanda baca.

Saya pikir masalah terbesar adalah kode inline, di mana seseorang mengajukan pertanyaan seperti:

Jika saya mengatakan untuk (i = 0; i> 100; i ++) {} apa artinya itu?

Itu kode dan bahasa Inggris, dan harus ditandai dengan tanda centang-kembali:

Jika saya mengatakan for (i=0; i>100; i++) {}apa artinya itu?

Saya pikir Anda harus terlebih dahulu membuat perbedaan antara (diformat) kode diformat yang hanya perlu benar-benar ditunjuk seperti itu, dan (juga) kode diformat buruk, yang memerlukan pemformatan manual pula.

Kode yang diformat memiliki terobosan dan lekukan. Yaitu: jika suatu garis didahului oleh satu breakline, Anda memiliki kandidat yang bagus. Jika memiliki ruang putih di atas itu, Anda memiliki kandidat yang sangat baik.

Teks normal menggunakan dua breaklines atau dua spasi dan breakline untuk memformat, jadi ada kriteria yang jelas untuk perbedaan.

Dalam kode LISP Anda tidak akan menemukan titik koma, dalam kode Ruby Anda mungkin tidak menemukan tanda kurung, dalam kode pseudo Anda mungkin tidak menemukan banyak sama sekali. Tetapi dalam bahasa (non-esoterik) apa pun, Anda akan menemukan kode yang layak untuk diformat dengan breaklines dan indentasi. Tidak ada yang seuniversal itu. Karena pada kode akhirnya adalah, ditulis untuk dibaca oleh manusia.

Jadi pertama-tama, cari kemungkinan baris kode . Juga, baris kode biasanya datang berkelompok. Jika Anda memilikinya, ada kemungkinan bagus bahwa yang di atas atau di bawahnya adalah sebaris kode juga.

Setelah Anda memilih jalur kode yang potensial, Anda dapat memeriksanya dengan kriteria yang dapat diukur dan memilih beberapa ambang batas :

• frekuensi karakter bukan kata
• frekuensi pengidentifikasi: kata yang sangat pendek atau kata yang sangat panjang dengan gaya CamelCase atau under_score
• pengulangan kata-kata yang tidak biasa

Juga, sekarang ada programmer dan cs, cakupan stackoverflow jelas dipersempit. Orang mungkin mempertimbangkan untuk menunjukkan semua tag bahasa sebagai bahasa. Dan ketika memposting, Anda akan diminta untuk memilih setidaknya satu tag bahasa, memilih language-agnostictag atau menghilangkannya secara eksplisit.

Dalam kasus pertama Anda tahu bahasa mana yang harus dicari, dalam kasus kedua, Anda mungkin ingin mencari kode semu dan dalam kasus terakhir, mungkin tidak akan ada kode apa pun, karena itu adalah pertanyaan yang terkait dengan beberapa teknologi atau kerangka kerja atau semacamnya.

Anda dapat membuat parser untuk setiap bahasa yang ingin Anda deteksi (definisi bahasa untuk ANTLR biasanya mudah ditemukan), kemudian jalankan setiap baris pertanyaan melalui masing-masing parser. Jika ada baris yang diurai dengan benar, Anda mungkin memiliki kode.

Masalah dengan ini adalah bahwa beberapa kalimat bahasa Inggris (bahasa alami) dapat diuraikan sebagai kode, jadi Anda mungkin ingin memasukkan beberapa ide lain juga, atau Anda dapat membatasi hasil positif hanya jika lebih dari satu atau dua baris berturut-turut menguraikan dengan benar dengan parser bahasa yang sama.

Masalah potensial lainnya adalah bahwa ini mungkin tidak akan mengambil pseudocode, tetapi itu mungkin OK.

Apa yang mungkin merupakan bukti paling masa depan dan memerlukan penyesuaian manual paling sedikit dalam jangka panjang, karena bahasa lain (yang terlihat agak berbeda dari bahasa pemrograman yang digunakan paling sekarang) menjadi lebih populer dan bahasa yang saat ini digunakan menjadi kurang populer, adalah melakukan sesuatu seperti yang dilakukan Google Translate (lihat paragraf berjudul "Bagaimana cara kerjanya?"), alih-alih mencari hal-hal tertentu seperti ab dan a (), dll.

Dengan kata lain, alih-alih secara manual memikirkan pola yang ditemukan dalam kode untuk dicari, komputer dapat menemukannya dengan sendirinya . Ini bisa dilakukan dengan memiliki

1. banyak kode dalam berbagai bahasa pemrograman

   • Saran: secara otomatis mengambil sampel kode dari repositori kode sumber berbasis web seperti Google Code atau Github, atau bahkan dari hal-hal di Stackoverflow yang sudah ditandai sebagai kode

   • Catatan: mungkin ide yang baik untuk mem-parsing komentar kode

2. banyak teks bahasa Inggris yang diambil dari artikel di web

   • walaupun bukan dari artikel tentang pemrograman (kalau tidak mereka mungkin memiliki kode di dalamnya dan mencampur sistem :-))

dan memiliki semacam algoritma secara otomatis menemukan pola dalam kode yang tidak dalam bahasa Inggris, dan sebaliknya, dan menggunakan pola-pola itu untuk mendeteksi apa itu kode dan apa yang bukan kode dengan menjalankan algoritma pada posting.

(Namun, saya tidak yakin bagaimana algoritma seperti itu akan bekerja. Jawaban lain untuk pertanyaan saat ini mungkin memiliki informasi yang berguna untuk itu.)

Kemudian sistem dapat memindai ulang kode sesekali untuk memperhitungkan perubahan dalam cara kode terlihat pada titik waktu tersebut.