Expressão regular para procurar Gadaffi

361

Estou tentando procurar a palavra Gadaffi. Qual é a melhor expressão regular para pesquisar isso?

Minha melhor tentativa até agora é:

\b[KG]h?add?af?fi$\b

Mas parece que ainda estou perdendo algumas revistas. Alguma sugestão?

Atualização: Encontrei uma lista bastante extensa aqui: http://blogs.abcnews.com/theworldnewser/2009/09/how-many-different-ways-can-you-spell-gaddafi.html

A resposta abaixo corresponde a todas as 30 variantes:

Gadaffi
Gadafi
Gadafy
Kadafi
Gaddafy
Gaddhafi
Kadafi
Gathafi
Ghadaffi
Ghadafi
Ghaddafi
Ghaddafy
Gheddafi
Kadaffi
Kadafi
Kaddafi
Kadhafi
Kazzafi
Khadaffy
Khadafy
Khaddafi
Qadafi
Qaddafi
Qadhafi
Qadhdhafi
Qadthafi
Qathafi
Quathafi
Qudhafi
Kad'afi
SiggyF
fonte
8
Quais estão faltando? E onde você está pesquisando, existe uma pesquisa na web com regex?
Czechnology 19/03/11
43
Sempre existem novos periódicos publicados; portanto, se eles continuarem escrevendo sobre o Gadaffi, você tenderá a .+ser a única expressão regular válida.
Moinudin
30
Descobri que esta imagem ajuda com as diferentes grafias: upload.wikimedia.org/math/6/1/f/...
KLee1
24
Como de costume, Lisp implementado este primeiro - foldr.org/~michaelw/projects/regex/regexp-test-suite.lisp (rolagem cerca de metade do caminho para baixo)
Daniel S. Sterling
7
@ Daniel Sterling: na verdade, o teste Khadafy faz parte do GNU grep testsuite desde o commit inicial do RCS (terça-feira, 3 de novembro, 21:38:52 1998 +0000), e provavelmente é ainda mais antigo que isso!
Paolo Bonzini

Respostas:

138

\b[KGQ]h?add?h?af?fi\b

A transcrição para o árabe é (diz a Wiki) "Qaḏḏāfī", então talvez adicione um Q. E um H ("Gadhafi", como o artigo (veja abaixo) menciona).

Btw, por que existe um $no final do regex?


Btw, bom artigo sobre o tema:

Kadafi, Kadafi ou Qaddafi? Por que o nome do líder líbio está escrito de tantas maneiras diferentes? .


EDITAR

Para corresponder a todos os nomes no artigo que você mencionou mais tarde , isso deve corresponder a todos eles. Vamos apenas torcer para que não corresponda a muitas outras coisas: D

\b(Kh?|Gh?|Qu?)[aeu](d['dt]?|t|zz|dhd)h?aff?[iy]\b
Czechnology
fonte
O $ está errado, eu estava combinando o fim das linhas primeiro, esqueci de removê-lo.
SiggyF
Será dtambém corresponder a um d?
SiggyF
2
@ DiggyF, não, eu apenas pensei que, se a transcrição em árabe diz Qaḏḏāfī, o regex deve procurar Qaddafitambém. Se você quiser procurar também a transcrição em árabe, procure por essa - não acho que haja mais variantes da transcrição em árabe, apenas das transcrições em inglês.
Czechnology 19/03/11
@ DiggyF, editei um regex mais longo que corresponde a todos os nomes no artigo que você postou (exceto os dois com ?letras em vez de). Pode ser um exagero embora.
Czechnology 19/03/11
2
Isso também combina com 'Quuzzafi' e um monte de outros falsos positivos, embora eu suponha que, ao pesquisar em reportagens, etc., isso não importa muito.
ben w
275

Fácil ... (Qadaffi|Khadafy|Qadafi|... )... é auto-documentado, pode ser mantido e, assumindo que o mecanismo regexp realmente compila expressões regulares (em vez de interpretá-las), ele será compilado no mesmo DFA que uma solução mais ofuscada faria.

Escrever expressões regulares compactas é como usar nomes curtos de variáveis ​​para acelerar um programa. Isso só ajuda se o seu compilador estiver com morte cerebral.

Chris Pacejo
fonte
23
Ótima resposta! As pessoas usam expressões regulares com muito mais frequência do que se preocupam com o modo como realmente funcionam.
Thomas Ahle 28/03
3
Também gosto muito da simplicidade dessa solução, mas estou surpreso que isso seja compilado no mesmo DFA. Você tem um link que fala sobre isso? Intuitivamente, isso parece ser menos eficiente do que o regex criado anteriormente ou a resposta abaixo, que sugere o uso do módulo regexp :: Assemble perl na mesma lista de nomes ou nomes.
Rian Sanderson
6
-1 O objetivo de um regex é reduzir o que geralmente pode ser - como é neste caso - uma lista muito longa de alternativas à fórmula relativamente curta. O resultado geralmente pode ser executado mais rapidamente do que fazer o que é essencialmente uma pesquisa exaustiva não otimizada.
27611 martineau
7
Você está certo, que o objetivo das regexes é fornecer uma representação clara e compacta para um grande conjunto de valores. Mas o conceito básico é apresentar uma regex e dizer "qualquer coisa que corresponda a isso é boa". Ou seja, assume que você tem a liberdade de incluir qualquer coisa sistemática. Aqui, temos a situação oposta: as grafias variantes (e as variações que nunca aparecem) são apenas esse lado do 'totalmente aleatório'. As tentativas elaboradas de "compactar" ganham pontos muito baixos por "limpar"!
jackr
11
Verifique também o Algoritmo de Aho-Corasick, que é ideal para simultaneamente busca string: en.wikipedia.org/wiki/...
Thomas Ahle
45

Uma coisa interessante a ser observada em sua lista de ortografia em potencial é que existem apenas 3 valores Soundex para a lista contida (se você ignorar o "Kazzafi").

G310, K310, Q310

Agora, existem falsos positivos ('Godby' também é G310), mas combinando os hits limitados do metafone, você também pode eliminá-los.

<?
$soundexMatch = array('G310','K310','Q310');
$metaphoneMatch = array('KTF','KTHF','FTF','KHTF','K0F');

$text = "This is a big glob of text about Mr. Gaddafi. Even using compound-Khadafy terms in here, then we might find Mr Qudhafi to be matched fairly well. For example even with apostrophes sprinkled randomly like in Kad'afi, you won't find false positives matched like godfrey, or godby, or even kabbadi";

$wordArray = preg_split('/[\s,.;-]+/',$text);
foreach ($wordArray as $item){
    $rate = in_array(soundex($item),$soundexMatch) + in_array(metaphone($item),$metaphoneMatch);
    if ($rate > 1){
        $matches[] = $item;
    }
}
$pattern = implode("|",$matches);
$text = preg_replace("/($pattern)/","<b>$1</b>",$text);
echo $text;
?>

Alguns ajustes e, digamos, transliteração cirílica, e você terá uma solução bastante robusta.

Tomwalsham
fonte
2
Observe que o soundex é especializado em inglês. Existem outros algoritmos fonéticos para outros idiomas com regras de pronúncia diferentes.
Incognito
8
Embora isso seja verdade, estamos em uma situação estranha aqui. O pedido principal era "Estou tentando procurar a palavra Gadaffi", mas sinto que o regex era um arenque vermelho. Não há um livro de regras sobre transliteração árabe-> latino e, dessa forma, reverter um regex de uma lista não responderá totalmente à solicitação original.
precisa saber é o seguinte
2
Sinto que um sistema de correspondência difusa é mais adequado, mas um algoritmo personalizado parece um exagero. O uso de uma combinação soundex-metaphone parece ter um desempenho tão bom quanto a solução regex, permitindo outras grafias imprevistas enquanto ainda se usa algos disponíveis no mercado.
precisa saber é o seguinte
O uso do metaphone2 e metaphone3 leva a melhores resultados (ou seja, quase tudo no metaphone2 é KDF, enquanto o metaphone1 não é bem assim). Metaphone3, no entanto, custa cerca de 40 dólares.
Incognito
27

Usando o módulo CPAN Regexp :: Assemble :

#!/usr/bin/env perl

use Regexp::Assemble;

my $ra = Regexp::Assemble->new;
$ra->add($_) for qw(Gadaffi Gadafi Gadafy Gaddafi Gaddafy
                    Gaddhafi Gadhafi Gathafi Ghadaffi Ghadafi
                    Ghaddafi Ghaddafy Gheddafi Kadaffi Kadafi
                    Kaddafi Kadhafi Kazzafi Khadaffy Khadafy
                    Khaddafi Qadafi Qaddafi Qadhafi Qadhdhafi
                    Qadthafi Qathafi Quathafi Qudhafi Kad'afi);
say $ra->re;

Isso produz a seguinte expressão regular:

(?-xism:(?:G(?:a(?:d(?:d(?:af[iy]|hafi)|af(?:f?i|y)|hafi)|thafi)|h(?:ad(?:daf[iy]|af?fi)|eddafi))|K(?:a(?:d(?:['dh]a|af?)|zza)fi|had(?:af?fy|dafi))|Q(?:a(?:d(?:(?:(?:hd)?|t)h|d)?|th)|u(?:at|d)h)afi))
Prakash K
fonte
23

Eu acho que você acabou complicando as coisas aqui. O regex correto é tão simples quanto:

\u0627\u0644\u0642\u0630\u0627\u0641\u064a

Corresponde à concatenação dos sete pontos de código Unicode em árabe que formam a palavra القذافي (ou seja, Gadaffi).

Staffan Nöteberg
fonte
3
Em seguida, basta acessar o nytimes.com pelo Google Translate e Bob é seu tio.
Robert Rossney
19

Se você deseja evitar a correspondência de coisas que ninguém usou (por exemplo, evitar tender para ". +"), Sua melhor abordagem seria criar uma expressão regular que seja apenas todas as alternativas (por exemplo, (Qadafi | Kadafi | ...) ), compile-o em um DFA e converta-o novamente em uma expressão regular. Supondo uma implementação moderadamente sensata que daria a você uma expressão regular "compactada", garantida para não conter variantes inesperadas.

andrew cooke
fonte
2
Eu sei que isso é theretically possível, mas como é que você faz isso na prática (usando, por exemplo som linguagem dinâmica comum)
Rory
3
Entendo a teoria por trás disso, mas, como @Rory, também estou interessado em saber como você realmente faria isso na prática.
21411 dancavallaro
Sim, pensei em fazê-lo, para dar uma resposta melhor, mas estou um pouco ocupado no momento. Eu tenho algum código (feio e mal documentado) em code.google.com/p/lepl/source/browse/src/lepl/regexp/core.py que constrói um dfa a partir de um regexp (na verdade, o analisador está em outra classe , mas o trabalho duro está aí; você vai regexp -> nfa -> dfa). passar do dfa para um regexp é fácil (eu acho?).
22611 Andrew Cooke
na verdade, a documentação é melhor do que eu me lembro: o) a idéia básica é que você descreva o regexp em termos das classes próximas à parte superior do arquivo. isso pode ser traduzido para um nfa com bastante facilidade (um nfa é realmente apenas um conjunto de transições dizendo "se você receber esta carta do que pode ir aqui ou aqui ...", é muito fácil de entender). o dfa é então uma espécie de versão "expandida" daquilo em que você evita ter que voltar atrás; isso é feito pelo NfaToDfa (e é a parte mais difícil). o dfa pode então ser pensada como a própria uma expressão regular que está escrito como conjuntos de caracteres muito complexos (?!)
Andrew Cooke
10

Se você tem uma lista concreta de todas as 30 possibilidades, basta concatená-las todas juntas com vários "ors". Então, você pode ter certeza de que corresponde apenas às coisas exatas listadas e não mais. Seu mecanismo de ER provavelmente será capaz de otimizar ainda mais e, bem, com 30 opções, mesmo que não o faça, ainda não é grande coisa. Tentar mexer manualmente transformando-o em um ER "inteligente" não pode ser melhor e pior.

Jeremy Bowers
fonte
9
(G|Gh|K|Kh|Q|Qh|Q|Qu)(a|au|e|u)(dh|zz|th|d|dd)(dh|th|a|ha|)(\x27|)(a|)(ff|f)(i|y)

Certamente não é a versão mais otimizada, divida em sílabas para maximizar as correspondências enquanto tenta garantir que não obtemos falsos positivos.

Sorrateiro
fonte
7

Bem, como você está combinando pequenas palavras, por que você não tenta um mecanismo de pesquisa de similaridade com a distância de Levenshtein ? Você pode permitir no máximo k inserções ou exclusões. Dessa forma, você pode alterar a função de distância para outras coisas que funcionam melhor para o seu problema específico. Existem muitas funções disponíveis na biblioteca simMetrics.

Arnoldo Muller
fonte
4

Uma alternativa possível é a ferramenta online para gerar expressões regulares a partir de exemplos http://regex.inginf.units.it . Dar uma chance!

mimmuz
fonte
1

Por que não fazer uma abordagem mista? Algo entre uma lista de todas as possibilidades e um Regex complicado que corresponde demais.

Regex é sobre correspondência de padrões e não consigo ver um padrão para todas as variantes na lista. Ao tentar fazer isso, também encontrará coisas como "Gazzafy" ou "Quud'haffi" que provavelmente não são uma variante usada e definitivamente não estão na lista.

Mas eu posso ver padrões para algumas das variantes e acabei com isso:

\b(?:Gheddafi|Gathafi|Kazzafi|Kad'afi|Qadhdhafi|Qadthafi|Qudhafi|Qu?athafi|[KG]h?add?h?aff?[iy]|Qad[dh]?afi)\b

No começo, listo aqueles em que não consigo ver um padrão e, em seguida, seguimos algumas variantes onde existem padrões.

Veja aqui em www.rubular.com

stema
fonte
Você \bestá incluído apenas na primeira e na última alternativa.
Christopher Creutzig
1

Eu sei que esta é uma pergunta antiga, mas ...

Nenhuma dessas duas regexes é a mais bonita, mas elas são otimizadas e ambas correspondem a TODAS as variações da postagem original.

"Pequena Beleza" # 1

(?:G(?:a(?:d(?:d(?:af[iy]|hafi)|af(?:f?i|y)|hafi)|thafi)|h(?:ad(?:daf[iy]|af?fi)|eddafi))|K(?:a(?:d(?:['dh]a|af?)|zza)fi|had(?:af?fy|dafi))|Q(?:a(?:d(?:(?:(?:hd)?|t)h|d)?|th)|u(?:at|d)h)afi)

"Pequena Beleza" # 2

(?:(?:Gh|[GK])adaff|(?:(?:Gh|[GKQ])ad|(?:Ghe|(?:[GK]h|[GKQ])a)dd|(?:Gadd|(?:[GKQ]a|Q(?:adh|u))d|(?:Qad|(?:Qu|[GQ])a)t)h|Ka(?:zz|d'))af)i|(?:Khadaff|(?:(?:Kh|G)ad|Gh?add)af)y

Descanse em paz, Muammar.

zx81
fonte
0

Apenas um adendo: você deve adicionar "Gheddafi" como ortografia alternativa. Portanto, a ER deve ser

\b[KG]h?[ae]dd?af?fi$\b
Vito De Tullio
fonte
0

[GQK] [ahu] + [dtez] + \ '? [Adhz] + f {1,2} (i | y)

Em partes:

  • [GQK]
  • [ahu] +
  • [dtez] +
  • \ '?
  • [adhz] +
  • f {1,2} (i | y)

Nota: Só queria dar uma chance a isso.

Dinko Pehar
fonte
-1

O que mais começa com Q, G ou K, tem ad, z ou t no meio e termina em "fi" que as pessoas realmente procuram?

/\b[GQK].+[dzt].+fi\b/i

Feito.

>>> print re.search(a, "Gadasadasfiasdas") != None
False
>>> print re.search(a, "Gadasadasfi") != None
True
>>> print re.search(a, "Qa'dafi") != None
True

Interessante que estou ficando com voto negativo. Alguém pode deixar alguns falsos positivos nos comentários?

Hank
fonte
2
De um dicionário rachaduras que acontecer de eu ter sentado ao redor: kartografi kryptografi Gaddafi Qaddafi gadafi gaddafi katastloofi katastorfi katastrofi khadaffi kadafi kardiyografi gaskromatografi kardiografi kinematografi kromatografi krystallografi kulturgeografi gandolfi grizzaffi gadhafi kadaffi kaddafi khaddafi qaddafi qadhafi quedaffi gordonsCHsKFI . Alguns deles não são falsos positivos.
BMDan 27/08/11
2
E as adições a essa lista que resultam do término em [iy]vez de apenas i:gelatinify gentrify ghostlify giddify gladify goutify gratify "Gyula Dessewffy" katasrofy katastrofy khadafy quantify quasi-deify quizzify
BMDan 27/08/11