Regex untuk semua 10 kata kata, dengan huruf unik

Saya mencoba menulis regex yang akan menampilkan semua kata yang panjangnya 10 karakter, dan tidak ada huruf yang berulang.

Sejauh ini, saya punya

grep --colour -Eow '(\w{10})'

Yang merupakan bagian pertama dari pertanyaan. Bagaimana cara saya memeriksa "keunikan"? Saya benar-benar tidak memiliki petunjuk, selain dari itu saya perlu menggunakan referensi kembali.

grep -Eow '\w{10}' | grep -v '\(.\).*\1'

tidak termasuk kata yang memiliki dua karakter identik.

grep -Eow '\w{10}' | grep -v '\(.\)\1'

mengecualikan yang memiliki karakter berulang.

POSIXly:

tr -cs '[:alnum:]_' '[\n*]' |
   grep -xE '.{10}' |
   grep -v '\(.\).*\1'

trmenempatkan kata-kata pada baris mereka sendiri dengan mengonversi setiap spersamaan karakter non-kata ( cpelengkap alfa-numerik dan garis bawah) ke karakter baris baru.

Atau dengan satu grep:

tr -cs '[:alnum:]_' '[\n*]' |
   grep -ve '^.\{0,9\}$' -e '.\{11\}' -e '\(.\).*\1'

(kecualikan garis kurang dari 10 dan lebih dari 10 karakter dan yang memiliki karakter muncul setidaknya dua kali).

Hanya dengan satu grep(GNU grep dengan dukungan PCRE atau pcregrep):

grep -Po '\b(?:(\w)(?!\w*\1)){10}\b'

Yaitu, batas kata ( \b) diikuti oleh urutan 10 karakter kata (asalkan masing-masing tidak diikuti oleh urutan karakter kata dan diri mereka sendiri, menggunakan operator PCRE pandangan ke depan negatif (?!...)).

Kami beruntung bekerja di sini, karena tidak banyak mesin regexp bekerja dengan referensi balik di dalam bagian berulang.

Perhatikan bahwa (setidaknya dengan versi GNU grep saya)

grep -Pow '(?:(\w)(?!\w*\1)){10}'

Tidak berhasil, tapi

grep -Pow '(?:(\w)(?!\w*\2)){10}'

tidak (as echo aa | grep -Pw '(.)\2') yang terdengar seperti bug.

Anda mungkin ingin:

grep -Po '(*UCP)\b(?:(\w)(?!\w*\1)){10}\b'

jika Anda ingin \watau \bmempertimbangkan huruf apa pun sebagai komponen kata dan bukan hanya huruf ASCII di lokal non-ASCII.

Alternatif lain:

grep -Po '\b(?!\w*(\w)\w*\1)\w{10}\b'

Itu adalah batas kata (yang tidak diikuti oleh urutan karakter kata yang berulang) diikuti oleh 10 karakter kata.

Hal-hal yang mungkin ada di benak seseorang:

• Perbandingan adalah case sensitive, jadi Babylonishmisalnya akan dicocokkan, karena semua karakter berbeda walaupun ada dua Bs, satu huruf kecil dan satu huruf besar (gunakan -iuntuk mengubah itu).
• untuk -w, \wdan \b, kata adalah huruf (yang ASCII hanya untuk GNU grep untuk saat ini , [:alpha:]kelas karakter di lokal Anda jika menggunakan -Pdan (*UCP)), angka desimal atau garis bawah .
• itu berarti bahwa c'est(dua kata berdasarkan definisi kata dalam bahasa Prancis) atau it's(satu kata berdasarkan definisi kata dalam bahasa Inggris) atau (satu kata sesuai definisi rendez-vouskata dalam bahasa Prancis) tidak dianggap sebagai satu kata.
• Bahkan dengan (*UCP), Unicode menggabungkan karakter tidak dianggap sebagai komponen kata, jadi téléphone( $'t\u00e9le\u0301phone') dianggap sebagai 10 karakter, salah satunya non-alpha. défavorisé( $'d\u00e9favorise\u0301') akan dicocokkan meskipun punya dua ékarena itu semua 10 karakter alfa yang berbeda diikuti oleh aksen akut kombinasi (non-alfa, jadi ada batas kata antara edan aksennya).

Oke ... inilah cara kikuk untuk string lima karakter:

grep -P '^(.)(?!\1)(.)(?!\1|\2)(.)(?!\1|\2|\3)(.)(?!\1|\2|\3|\4).$'

Karena Anda tidak dapat menempatkan referensi kembali di kelas karakter (misalnya [^\1|\2]), Anda harus menggunakan pandangan ke depan negatif - (?!foo). Ini adalah fitur PCRE sehingga Anda perlu -Pberalih.

Pola untuk string 10 karakter akan jauh lebih lama, tentu saja, tetapi ada metode yang lebih pendek menggunakan pencocokan panjang variabel apa pun ('. *') Di lookahead:

grep -P '^(.)(?!.*\1)(.)(?!.*\2)(.)(?!.*\3)(.)(?!.*\4)(.)(?!.*\5).$'

Setelah membaca jawaban Stephane Chazelas yang mencerahkan, saya menyadari ada pola sederhana yang serupa untuk digunakan melalui -vsakelar grep :

    (.).*\1

Karena cek menghasilkan satu karakter pada satu waktu, ini akan melihat apakah ada karakter yang diberikan diikuti oleh nol atau lebih karakter ( .*) dan kemudian kecocokan untuk referensi belakang. -vmembalikkan, hanya mencetak hal-hal yang tidak cocok dengan pola ini. Ini membuat referensi belakang lebih berguna karena mereka tidak dapat dinegasikan dengan kelas karakter, dan secara signifikan:

grep -v '\(.\).*\1'

akan bekerja untuk mengidentifikasi string dengan panjang apa pun dengan karakter unik sedangkan:

grep -P '(.)(?!.*\1)'

tidak akan, karena itu akan cocok dengan akhiran apa pun dengan karakter unik (mis. abcabccocok karena abcdi akhir, dan aaaakarena adi akhir - maka string apa pun ). Ini adalah komplikasi yang disebabkan oleh lookaround menjadi nol-lebar (mereka tidak mengkonsumsi apa pun).

Jika Anda tidak perlu melakukan semuanya dalam regex, saya akan melakukannya dengan dua langkah: pertama-tama cocokkan semua kata 10 huruf, kemudian filter untuk keunikan. Cara terpendek yang saya tahu bagaimana melakukan ini adalah di Perl:

perl -nle 'MATCH:while(/\W(\w{10})\W/g){
             undef %seen;
             for(split//,$1){next MATCH if ++$seen{$_} > 1}
             print
           }' your_file

Perhatikan \Wjangkar tambahan untuk memastikan bahwa hanya kata-kata yang panjangnya tepat 10 karakter yang cocok.

Yang lain menyarankan ini tidak mungkin tanpa berbagai ekstensi untuk sistem ekspresi reguler tertentu yang sebenarnya tidak teratur. Namun, karena bahasa yang ingin Anda cocokkan terbatas, itu jelas teratur. Untuk 3 huruf dari alfabet 4 huruf, akan mudah:

(abc|abd|acb|acd|bac|bad|bcd|bdc|cab|cad|cbd|cdb|dab|dac|dbc|dcb)

Jelas ini tidak terkendali dengan terburu-buru dengan lebih banyak huruf dan huruf yang lebih besar. :-)

Opsi --perl-regexp(pendek -P) dari GNU grepmenggunakan ekspresi reguler yang lebih kuat yang mencakup pola melihat ke depan. Pola berikut mencari setiap huruf yang tidak muncul di sisa kata:

grep -Pow '((\w)(?!\w*\g{-1})){10}'

Namun perilaku run-time sangat buruk, karena \w*dapat memiliki panjang yang hampir tak terbatas. Dapat dibatasi \w{,8}, tetapi itu juga memeriksa di luar batas kata 10 huruf. Karena itu, pola berikut pertama memeriksa panjang kata yang benar:

grep -Pow '(?=\w{10}\b)((\w)(?!\w*\g{-1})){10}'

Sebagai file uji saya telah menggunakan file besar ≈ 500 MB:

• Pola pertama: ≈ 43 dtk
• Pola terakhir: ≈ 15 dtk

Memperbarui:

Saya tidak dapat menemukan perubahan signifikan dalam perilaku run-time untuk operator yang tidak serakah ( \w*?) atau operator yang posesif ( (...){10}+). Agak sedikit lebih cepat tampaknya penggantian opsi -w:

grep -Po '\b(?=\w{10}\b)((\w)(?!\w*\g{-1})){10}\b'

Pembaruan grep dari versi 2.13 ke 2.18 jauh lebih efektif. File tes hanya butuh ≈ 6 s.

Solusi Perl:

perl -lne 'print if (!/(.)(?=$1)/g && /^\w{10}$/)' file

tetapi tidak berhasil

perl -lne 'print if (!/(.)(?=\1)/g && /^\w{10}$/)' file

atau

perl -lne 'print if ( /(.)(?!$1)/g && /^\w{10}$/)' file

diuji dengan perl v5.14.2 dan v5.18.2