Regex para todas as palavras de 10 letras, com letras únicas

Question

Estou tentando gravar um regex que exibirá todas as palavras com 10 caracteres e nenhuma das letras está repetindo.

Até agora, tenho

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

Qual é a primeira parte da questão. Como eu iria verificar a "exclusividade"? Eu realmente não tenho a menor idéia, além disso eu preciso usar referências de volta.

    

Answer 1

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

exclui palavras com dois caracteres idênticos.

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

exclui os que têm caracteres repetidos.

POSIXly:

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

tr coloca palavras em sua própria linha convertendo qualquer equação de s de caracteres não-palavra ( c omplemento de alfanumérico e sublinhado) para uma nova linha personagem.

Ou com um grep :

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

(exclua linhas com menos de 10 e mais de 10 caracteres e aquelas com um caractere aparecendo pelo menos duas vezes).

Com apenas grep (grep do GNU com suporte a PCRE ou pcregrep ):

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

Ou seja, um limite de palavra ( \b ) seguido por uma sequência de 10 caracteres de palavra (desde que cada um não seja seguido por uma seqüência de caracteres de palavra e por eles mesmos, usando o operador de look-ahead (?!...) ) .

Temos sorte de que isso funcione aqui, já que muitos mecanismos de regexp não funcionam com referências anteriores dentro de partes repetitivas.

Note que (com a minha versão do GNU grep, pelo menos)

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

Não funciona, mas

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

faz (como echo aa | grep -Pw '(.)' ) o que soa como um bug.

Você pode querer:

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

se você quiser que \w ou \b considere qualquer letra como um componente de palavra e não apenas os caracteres ASCII em locais não-ASCII.

Outra alternativa:

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

Esse é um limite de palavra (um que não é seguido por uma sequência de caracteres de palavra, um dos quais se repete) seguido por caracteres de 10 palavras.

Coisas que possivelmente podem ter no fundo da mente:

• A comparação faz distinção entre maiúsculas e minúsculas, portanto, Babylonish , por exemplo, corresponderia, pois todos os caracteres são diferentes, embora haja dois B s, um inferior e um maiúsculo (use -i para alterar isso).
• para -w , \w e \b , uma palavra é uma letra (somente ASCII para GNU grep por enquanto , a classe de caractere [:alpha:] em sua localidade se estiver usando -P e (*UCP) ), dígitos decimais ou sublinhado .
• significa que c'est (duas palavras de acordo com a definição francesa de uma palavra) ou it's (uma palavra de acordo com algumas definições inglesas de uma palavra) ou rendez-vous (uma palavra de acordo com a definição francesa de uma palavra) não são considerados uma palavra.
• Mesmo com (*UCP) , os caracteres combinados Unicode não são considerados como componentes de palavras, portanto, téléphone ( $'t\u00e9le\u0301phone' ) é considerado como 10 caracteres, um deles não alfa. défavorisé ( $'d\u00e9favorise\u0301' ) seria correspondido, embora tenha dois é , porque são 10 caracteres alfa diferentes seguidos por um acento agudo de combinação (não alfa, portanto há um limite de palavras entre o e e seu sotaque ).

Answer 2

Ok ... aqui está o caminho desajeitado para uma string de cinco caracteres:

grep -P '^(.)(?!)(.)(?!|)(.)(?!||)(.)(?!|||).$'

Como não é possível colocar uma referência de retorno em uma classe de caractere (por exemplo, [^|] ), você deve usar um look-ahead negativo - (?!foo) . Este é um recurso do PCRE, então você precisa da opção -P .

O padrão para uma sequência de 10 caracteres será muito mais longo, é claro, mas há um método mais curto usando uma correspondência de qualquer coisa com comprimento variável ('. *') na aparência:

grep -P '^(.)(?!.*)(.)(?!.*)(.)(?!.*)(.)(?!.*)(.)(?!.*).$'

Depois de ler a resposta esclarecedora de Stephane Chazelas, percebi que existe um padrão simples semelhante para esse uso através da opção -v do grep:

    (.).*

Como a verificação continua um caractere de cada vez, isso mostra se algum caractere é seguido por zero ou mais caracteres ( .* ) e, em seguida, uma correspondência para a referência anterior. -v inverte, imprimindo apenas coisas que não correspondem a esse padrão. Isso torna as referências posteriores mais úteis, pois elas não podem ser negadas com uma classe de caracteres e significativamente:

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

trabalhará para identificar uma string de qualquer tamanho com caracteres únicos, enquanto:

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

não corresponderá, pois corresponderá a qualquer sufixo com caracteres únicos (por exemplo, abcabc corresponde a abc no final e aaaa devido a a no final - portanto any string). Esta é uma complicação causada por lookarounds sendo zero-width (eles não consomem nada).

    

Answer 3

Se você não precisa fazer a coisa toda na regex, eu faria isso em duas etapas: primeiro, combine todas as palavras de 10 letras e, em seguida, filtre-as para obter exclusividade. O caminho mais curto que eu sei fazer é em Perl:

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

Anote as âncoras \W adicionais para garantir que apenas as palavras com exatamente 10 caracteres sejam correspondidas.

    

Answer 4

Outros sugeriram que isso não é possível sem várias extensões para certos sistemas de expressões regulares que não são de fato regulares. No entanto, como a linguagem que você deseja corresponder é finita, é claramente regular. Para 3 letras de um alfabeto de 4 letras, seria fácil:

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

Obviamente, isso fica fora de mão rapidamente, com mais letras e alfabetos maiores. : -)

    

Answer 5

A opção --perl-regexp (short -P ) do GNU grep usa expressões regulares mais poderosas que incluem padrões de look ahead. O padrão a seguir procura por cada letra que esta carta não aparece no restante da palavra:

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

No entanto, o comportamento em tempo de execução é bastante ruim, porque \w* pode ter comprimento quase infinito. Pode ser limitado a \w{,8} , mas também verifica além do limite de palavras de 10 letras. Portanto, o seguinte padrão primeiro verifica o comprimento correto da palavra:

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

Como arquivo de teste, usei um & aprox. Arquivo de 500 MB:

• Primeiro padrão: & aprox. 43 s
• Padrão anterior: & 15 s

Atualização:

Não consegui encontrar uma alteração significativa no comportamento do tempo de execução para um operador não ganancioso ( \w*? ) ou operador possessivo ( (...){10}+ ). Um pouquinho mais rápido parece a substituição da opção -w :

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

Uma atualização do grep da versão 2.13 para a 2.18 foi muito mais eficaz. O arquivo de teste levou apenas & aprox. 6 s.

    

Answer 6

Uma solução Perl:

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

mas não funciona com

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

ou

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

testado com perl v5.14.2 e v5.18.2