mars 16, 2009

Lite om vad som händer på andra bloggen: My Constraint Programming Blog

Som tidigare nämnts är det inte här utan på My Constraint Programming Blog ("Min villkorsprogrammeringsblogg") jag numera mest håller till.

Här är en liten sammanfattning om vad som hänt där och i samband med detta.

* En stor drös med Comet modeller på My Comet page. Några exempel:


* En mycket mindre drös med MiniZinc-modeller på My MiniZinc page.

Men de modeller som tagit mest tid är följande

Nonogram
Här är de blogganteckningarna som presenterar de olika varianterna, i normal sorterad tidordning:
1) More Comet models, e.g. Nonogram, Steiner triplets, and different set covering problems som presenterade den första Nonogram-modellen. Långsam var den.
2) Comet: regular constraint, a much faster Nonogram with the regular constraint, some OPL models, and more presenterade en mycket snabbare Nonogram-modell som använder principen bakom reguljära uttryck (villkoret regular).
3) samt slutligen Comet: Nonogram improved: solving problem P200 from 1:30 minutes to about 1 second där jag hittade lite mer saker att förbättra, bl.a. med hjälp av en av mina husgudar Pascal Van Hentenryck och som är en av skaparna av just Comet.

Ungefär samtidigt kom jag i kontakt med gänget bakom Gecode (C++ baserat), det snabbate constraint programming-systemet som jag känner till. Roligt nog har de nu lagt in samma förbätring i sitt Nonogramprogram.


Pi Day Sudoku
I lördags var det Pi-dagen (3.14 som vissa skriver den 14 mars) och som hyllning skapade Brainfree Puzzles några dagar tidigare en tävling: Pi Day Sudoku 2009. Det är som vanliga Sudoku fast med knorr: förutom att det ska vara 1..9 på samtliga rader och kolumner ska det finnas exakt tre stycken Pi. Till detta kommer att man inte har de vanliga kvadratiska regionerna som kräver samma fördelning av siffror utan det är även olika former på regionerna (kolla sajten så förstår ni bättre). Jag har slutat med att lösa Sudokuproblem för hand, däremot var de speciella kriterierna ett intressant problem att modellera med villkorsprogrammering (constraint programming).

Första modellen, som var rätt långsam, skrevs om i Pi Day Sudoku 2009. Efter lite funderande, och framförallt diskuterande med Mikael Zayenz Lagerkvist (från sagda Gecode team), snabbades modellen upp avsevärt. Detta beskrevs i Solving Pi Day Sudoku 2009 with the global cardinality constraint.

Till förfång för alla de som som söker på Pi Day Sudoku har varken lösningen på problemet eller modellerna presenterats på bloggen (det blir inte förrän tävlingen är över).


Gecode 3.0.0
Vi får ju inte heller glömma att version 3.0.0 av Gecode släpptes för några dagar sedan. Jag rekommenderar varmt den mycket trevliga introduktion till modellering i Gecode: Modeling with Gecode (PDF).

I och med att version 3 har släppts kommer det inom kort även stöd för det grafiska verktyget Gist till MiniZinc, dvs när man har Gecode/FlatZinc som lösare (och det har man alltid som förstaval). Det ser jag mycket fram emot.


Till sist: MiniZinc Challenge 2008
Resultat av constraint programming-tävlingen MiniZinc Challenge 2008 kom förra vecka. Inte förvånande vann Gecode. Mer om detta skrevs i MiniZinc Challenge 2008 Results.

Posted by hakank at 08:34 EM Posted to Constraint Programming | Reguljära uttryck etc

september 11, 2005

Ordavstånd (edit distances): Levenshtein och Hirschberg med lite extra finesser

Sedan länge har jag varit intresserad av hur lika ord är varandra. Ett sätt är att se hur många operationer som krävs för att transformera det ena ordet till det andra, och på detta vis få "ordavståendet" mellan orden. Se nedan för lite andra skriverier och program i detta och näraliggande ämnen.


Exempel
Ordavståndet mellan ordet håkan och ordet hakank är 2 eftersom det krävs två operationer för att transformera det första ordet till det andra: byt ut "å" till "a" och lägg till ett "k" på slutet. De möjliga operationerna för att omvandla ett ord till ett annat är:
* byt ut (replace)
* lägg till (insert)
* ta bort (delete)

samt "behåll" (keep) som egentligen inte är en operation eftersom ingenting görs. De engelska begreppen används nedan.


Edit distances
Sådana transformationer/jämförelser kallas för (används i) edit distance (googlesökning). En av de mer moderna användningarna är att jämföra två DNA-sekvenser med varandra för att se hur mycket eller på vilket sätt de matchar eller inte matchar, och det ligger mycket forskning (och pengar!) kring att göra ruskigt snabba och bra strängjämförelsemetoder.

Två av de mest kända algoritmerna för sådant är Levenshtein och Hirschberg (namnen från respektive upphovsperson).


Programmet Edit distances
Var lugn, jag tänker inte förklara algoritmerna här. Däremot vore det skoj att visa hur de fungerar och hur de kommer fram till ordavståndet. Detta är gjort i programmet Edit distances, som nu kommer att förklaras lite mer.


Körning av programmet
Låt oss jämföra orden håkan och hakank som nämndes ovan. En körning av programmet ger följande resultat:


...
Operations (graphical):
håkan-
| ||| 
hakank

Explanation:
'-': insert or delete
'|': keep
' ': replace

Long description (string position in parenthesis):
keep 'h' (1)
replace 'å' with 'a' (2)
keep 'k' (3)
keep 'a' (4)
keep 'n' (5)
insert 'k' (6)


Short description (k: keep, i: insert, d: delete, r: replace):
krkkki

It was 2 edit operations:
keep: 4
replace: 1
insert: 1
('keep' is not counted as an operation)


Förklaring
Här förklaras resultatet mer i detalj. Först visas den grafiska representationen av tranformationen:

håkan-
| ||| 
hakank

Ett "-" i den första raden betyder att en bokstav läggs till ("insert") i det andra ordet, dvs det avslutande "k". Tecknet "|" innebär att bokstäverna är samma (operationen "keep") i samma position. Om det är tomt i mellanraden innebär det att man byter ut en bokstav (här att "å" ersätts av "a"). Ett "-" i sista raden innebär att man tar bort en bokstav ("delete").


Efter det visas en "pratversion" av operationerna i korrekt ordning, där talen inom parentes anger radpositionen (eller "operationsnumret" om man så vill). Notera att positionen inte är för orden utan för den sträng som visas i den grafiska representationen.

keep 'h' (1)
replace 'å' with 'a' (2)
keep 'k' (3)
keep 'a' (4)
keep 'n' (5)
insert 'k' (6)

Så kommer en kortversion av operationern med koderna: k: keep, i: insert, d: delete, r: replace:

krkkki

vilket helt enkelt är första bokstäverna i de engelska namnen för operationerna.

Slutligen visas lite statistik där 2:an är det eftersöka ordavståndet. Och som sagt är keep inte någon egentlig operation, så 2 kommer här från antal replace och antal insert (1+1=2).


It was 2 edit operations:
keep: 4
replace: 1
insert: 1


Två algoritmer?
Varför två algoritmer, de ger ju samma resultat? Skoj att du noterat det. Visst, de ger ofta samma resultat, men inte riktigt alltid. T.ex. för jämförelsen mellan " abc e" och "abdec" (notera mellanslagen) så ger Hirschberg följande operationer: dddkkddrki:

   abc  e-
   ||   | 
---ab--dec

medan Levenshtein ger dddkkdrrr, dvs:

   abc  e
   ||    
---ab-dec

De ger olika antal keep-operationer (3 respektive 2), vilket kan vara viktigt. Det är dock samma antal edit distance operationer.

Om man vill man se den exakta skillnaden mellan dessa två operationslistor passar det ju bra att använda programmet för detta.


Tips: Lägg till mellanslag före eller efter
För vissa jämförelser kan det bli väldigt tråkiga operationer, t.ex. kjellerstrand -> hakank.blogg är det i stort sett bara utbyten: drrrrrrrrrrrr. Om man däremot lägger till lite mellanslag före eller efter endera ordet kan man se lite andra mappningar.

Exempel: lägg till ett gäng (t.ex. 13 mellanslag) före "kjellerstrand" så kommer följande mappning.

                          kjellerstrand

                          |   |        

---------------------hakank-.bl-----ogg


Naturligtvis innebär detta att antal operationer inte stämmer med ursprungsjämförelsen, men det är kanske av underordnad betydelse. I och för sig skulle programmet kunna justera för sådant trixande, men det finns alltid risker med sådan intelligens...


Fet credit
En stor fet credit måste göras till Lloyd Allison som kodat Javascript-versionerna av Levenshtein och Hirschberg.

Mitt program använder inte koden rakt av, men den är mer eller mindre strikt konverterad till Perl-kod. Programmet har även vissa finesser som saknas på Allisons sidor, t.ex. prat- och kortversionen av operationerna. Jag har inte brytt mig om att visa riktigt alla Allisons finesser, dvs tracen för Hirschberg.

Se även liknande program och skriverier
Skapa stavfel som råkar använda samma operationer som i ovan nämnda program. Där finns även några andra referernser.
Läsning av förvanskade ord
Nearest words
New Markov words II

Eventuellt relevant är också kategorin: Reguljära uttryck etc.

Lite länkar
Dan Hirschberg, speciellt dennes publikationer
Dan Gusfield: Algorithms on Strings, Trees, and Sequences
Alberto Apostolico, Zvi Galil (ed): Pattern Matching Algorithms.



(Det var det. Nu kan jag fundera lite på Thebes Visualiserad singulärvärdesuppdelning.)

Posted by hakank at 10:14 EM Posted to Program | Reguljära uttryck etc | Språk | Comments (4)

november 08, 2004

Perl 6 grammars and regular expressions

Cultured Perl: Perl 6 grammars and regular expressions

Perl 6 is finally coming within reach. In this article, Ted gives you a tour of the grammars and regular expressions of the Perl 6 language, comparing them with the currently available Parse::RecDescent module for Perl 5. Find out what will be new with Perl 6 regular expressions and how to make use of the new, powerful incarnation of the Perl scripting language.

Via slashdot.

Posted by hakank at 07:21 EM Posted to Reguljära uttryck etc

maj 28, 2004

Reguljärt uttryck för pokerhänder

Michael Ash ger sig i sin Regex Blog på att skapa ett reguljärt uttryck för vinnande pokerhänder. Kul sak. Se vidare anteckningen Shuffle up and deal.

Liksom en av kommentatorerna kommer även jag att fundera lite på detta...

Se även
Reguljära uttryck samt kategorin Reguljära uttryck etc.

Posted by hakank at 05:51 EM Posted to Reguljära uttryck etc

maj 16, 2004

MT-Blacklist blacklist checker

Detta är troligen endast intressant för de som bloggar med Movable Type och har bloggspamfiltret MT-Blacklist . Och det är kanske inte ens intressant för dem...

I Avoiding blacklist bloat skriver Jay Allen om att det är viktigt att då och då redigera sin blacklist-fil för att minska redundansen i filen.

Det är inte alltid helt enkelt att lista ut vilka rader/reguljära uttryck som är redundanta,. Som ett proof-of-concept (OK, ett hack) skrevs därför programmet MT-Blacklist blacklist checker som gör några automatiska kontroller:

Än så länge är det inte möjligt att skriva in en URL till en blacklist, utan progammet kan endast kontrollera min blacklist samt master-blacklistan.

Om du skulle vilja kontrollera din blacklist-fil på detta sätt, maila mig URL-en till filen, så ser vi vad vi kan göra.

(Uppmärksamma läsare märker snart att min blacklist-fil i skrivande stund behöver friseras ganska ordentligt, vilket kommer att göras vid tillfälle.)

Posted by hakank at 05:55 EM Posted to Blogging | Reguljära uttryck etc | Comments (3)

april 28, 2004

Skapa strängar från reguljära uttryck - eller: Tystnaden de senaste dagarna

I morse mailade en vän frågan var jag hållit hus de senaste dagarna. Hans misstanke om alien abduction var rörande att läsa. Här är ett något kompletterat utdrag från mitt svarsmail.


Anledningen till tystnaden de senaste dagarna är att jag varit djupt inne i ett skoj projekt, nämligen att generera strängar givet ett reguljärt uttryck (regex). Embryot till systemet var det som skrevs om häromdagen angående stavningen av "Henning Mankell". Detta har även gjorts djupare studier i programspråket Icon/Unicon.

Innan dess läste jag, nästan helt orelaterat, en avhandling om ett nytt sätt att söka i ett dokument, där man kan markera upp de relevanta delarna varpå systemet försöker lista ut vad det är man söker efter. Systemet heter LAPIS, och eventuellt kommer det en lite längre anteckning om detta trevliga system.


Systemet för genererande av strängar från regex har kommit en bra bit framåt. Det är två principiellt fungerande delar som jag försöker att integrera så det blir ett fint webb-program. Dels ett Perlprogram som parsrar det reguljära uttrycket och skapar Icon-kod, dels ett Icon-program som innehåller funktioner för att skapa strängarna. Idealet vore naturligtvis att ha ett enda program, möjligen skrivet i ett helt annat programspråk, t.ex. Java, men det är ett annat projekt.

I kommentaren till Fortsatt stavning av "Henning Mankell". Samt lite om agrep visas en lista som då skapades via en handsnickrad Icon-funktion. Nu kan man alltså göra sådant nästan helt automatiskt.


Här nedan följer en kort förklaring hur systemen fungerar. Det finns dock inte någon webbversion av programmet så ni får helt enkelt lita på mina ord i det följande.

Först bör nämnas en viktig restriktion i strängskapandet: Kvantifikationsoperatorerna * ("ingen eller flera förekomster"), + ("en eller flera förekomster") samt {,}genererar inte oändligt antal strängar utan endast ett begränsat och parameterstyrt antal, för närvarande 3. Regexet (ab)* skapar alltså endast följande strängar:

"","ab", "abab","ababab"

Perl-programmet består nästan bara av en parser och "action-koder" för att bilda Icon-koden. Den parser som används blev, efter ett antal olika försök med andra liknande system, Parse::RecDescent. En trevlig tutorial till detta system finns här .

En stor del av tiden har ägnats åt att debugga grammatiken (dvs reglerna för hur regex-språket ser ut). Tyvärr är detta program långsamt, vilket beror på en kombination av 33% mitt fel, 33% en inte helt trivial grammatik samt cirka 33% att det är en långsam parsergenerator. De största problemen var att få grammatiken att bli "left recursion free", få ordning på det egna lilla språk som finns i character classes (dvs inom []) samt escapeande av tecken här och var. Det finns troligen en och annan bugg kvar att fixa.

Naturligtvis testades först att skriva parserna i Icon eftersom det är där själva genereringen av strängarna görs , men inga av de parsers i kombination med olika varianter av grammatiker fungerade speciellt bra. Spelet är dock inte slut ännu: Nu finns det ju en grammatik som inte är "left-recursive" längre, vilket är ett bra steg framåt.

Exempel: Om input till parserna är det reguljära uttrycket

K(je|ä)ll(er)?(st|b)r?an?d

skapas följande Icon-kod:

suspend ("K" || (((("j" || "e") | "ä")) || ("l" || ("l" ||
(gen_question_mark((("e" || "r"))) || (((("s" || "t") | "b")) ||
(gen_question_mark("r") || ("a" || (gen_question_mark("n") || "d")))))))))

Icon-programmet är i princip klart och klarar av det allra mesta av den önskvärda funktionaliteten. Det enklaste vore att pumpa in strängen som genererades av parsern i en eval()-liknande funktion, men sådana möjligheter saknas tydligen i Icon. Koden behöver naturligtvis snyggas upp och eventuellt OOP-as.


Det är nu skoj att testa de regexar som finns t.ex. på Regular Expression Library eller Rx Cookbook. Ett exempel: På Regex Lib finns ett för validering av email:

(\w[-._\w]*\w@\w[-._\w]*\w\.\w{2,3})

De första strängarna (från en ohyggligt lång lista) som mitt system skapar är:

AA@AA.AA
AA@AA.AAA
AA@AA.BB
AA@AA.BBB
AA@AA.CC
AA@AA.CCC
AA@AA.DD
AA@AA.DDD
....

Icon-progammet har även en slump-mode som genererar sådant som:

Hw@qC.JJ
Hw@q___p.M
H_N@d.LL
Gy@DV.II
Gy@D___S.jj
GFFFL@CU.hh
....


Det finns åtminstone två problem med regexet ovan (och det behöver man egentligen inte ha avancerade program för att komma på):

(Härfinns ett Perl-program som bygger upp ett oerhört mer komplicerat regex för att kontrollera RFC-komplienta mailadresser. Det är möjligen något overkill.)


Om någon känner till något liknande strängskapande system givet ett regex, är denne välkommen att höra av sig, antingen i kommentaren på bloggen eller via mail.


Se även
Regexbibeln Mastering Regular Expressions, Second Edition, av Jeffrey Friedl, som har en companionwebbplats på http://regex.info.

Posted by hakank at 09:56 EM Posted to Reguljära uttryck etc

april 23, 2004

Fortsatt stavning av "Henning Mankell". Samt lite om agrep

I Programspråket Icon och stavningen av "Henning Mankell" skrevs om möjliga stavningar av "Henning Mankell". Här följer en uppdatering kring detta.

Language Log finns det, förutom den artikel som inspirerade mig att skriva programmet: The mysteries of... what's his name?, några andra bloggningar i ämnet:

I Henning Mangled görs en intressant google-analys av de olika stavningarna.

Henning Mankellismus in icon innehåller en uppmaning om hjälp kring det prinicpiella problemet: I've been hoping, though, that someone will follow up on David Beaver's post by writing a program to help with (various approaches to) estimating the statistical density of what David called "the Henning Mankell morpheme space".. Där finns, roligt nog, också ett pek till min förra anteckning.

agrep - approximate grep
I näst sista stycket på The mysteries of... what's his name? nämns sökprogrammet grep som kan hantera reguljära uttryck.

Om man nu inte vill skriva slika uttryck kan man använda agrep, approximate grep, som även tillåter felstavningar. Programmet är skapat av Sun Wu och Udi Manber (en gammal husgud) från University of Arizona,

Man anger antalet tilllåtna felstavningar genom parametern -# där # är ett heltal från 0 till 8, där 0 innebär att det inte ska vara någon felstavning alls.

Låt oss nu testa detta på den fil som skapades av Icon-programmet (se föregående blogganteckning) när vi tillåter 1 fel:

agrep -1 "Henning Mankell" pattern_generation.txt

Då hittas följande varianter:

Henking Mankell
Hening Mankell
Henning Menkell
Henning Mankell
Henning Mankall
Henning Manell
Henning Mannell
Hanning Mankell

Om man använder parametern -8 (dvs 8 fel) hittas 547 av de 648 varianterna. Men med så många tillåtna fel kommer programmet att hitta en massa andra irrelevanta ord också, så det är inte speciellt användbart. Det normala är att man tillåter 1 eller kanske 2 fel.

En annan feature i agrep är parametern -p ("find records in the text that contain a supersequence of the pattern") som hittar alla strängar som matchar initialerna. T.ex. agrep -p HM fil hittar alla strängar som kan bildas av två intilliggande ord som börja på "H" respektive "M". För den specifika uppgiften är detta också overkill.


Agrep använder edit distance för att avgöra antalet felstavningar, dvs räknar ut avstånden mellan orden. För mer om detta se t.ex. de Postscript-filer som finns i agrep-katalogen. Se även blogganteckningen Skapa stavfel.


Det finns ett annat system för approximerad sökning: TRE (0.6.6 i skrivande stund) som har en version av agrep som verkar skoj.
TRE includes a version of the agrep command line tool for approximate regexp matching in the style of grep. Unlike other agrep implementations (like the one by Sun Wu and Udi Manber from University of Arizona available here) TRE agrep allows full regexps of any length, any number of errors, and non-uniform costs for insertion, deletion and substitution.

Posted by hakank at 10:22 FM Posted to Reguljära uttryck etc | Språk | Comments (2)

april 22, 2004

Programspråket Icon och stavningen av "Henning Mankell"

Jonas Söderström på Blind Höna riktade uppmärksamheten på problemet att veta exakt hur en känd svensk författare stavar sitt namn. Är det "Menking Hannell", "Manking Hannall", "Manning Henkell"? Artikeln visar en massa alternativ.

Det är enkelt att skapa alla dessa varianter genom permutationer. Anledningen till denna blogganteckning är att visa hur elegant man kan göra detta i programspråket Icon. Själv använder jag Unicon, en efterföljande och superset av Icon, som i sin tur är en utveckling av och efterföljare till det fantastiska språket SNOBOL.

Problemformulering
Generera alla möjliga varianter av följande reguljära uttryck

  [HM][ea](nk|n|nn)(ing|ell|all)

där [HM] betyder endera bokstaven "H" eller bokstaven "M", och ing|ell|all innebär någon av strängarna "ing", "ell" eller "all". (Egentligen kan man skriva [HM] som (H|M), men vanligen används [...] för sådana "character classes".)

Både för- och efternamn genereras av detta uttryck med restriktionen att de inte får börja på samma bokstav.

En Icon-lösning på detta problem ser ut så här.

procedure main()
   every x:= HM() do write(x)
end

procedure HM()
   suspend ("H" || _HM() || " " || "M" || _HM()) |
      ("M" || _HM() || " " || "H" || _HM())
end

procedure _HM()
  suspend (!"ea" || !["nk","n", "nn"] || !["ing","ell","all"]);
end

Lite förklaringar av Icon-koden:
Operatorn ! (utropstecken) gör själva genereringen, när man använder every.

!"ea" motsvarar det reguljära uttrycket [ea], och genererar både "e" och "a", dvs alla tecken som finns i strängen. Kontruktionen !["ing","ell","all"] motsvarar det reguljära uttrycket (ing|ell|all) och genererar alla element i listan.

| (enkelt "pipe"-tecken) innebär alternation, dvs "eller". Man skulle kunna uttrycka !"ea" på följande sätt: !("e"|"a").

|| (dubbla "pipe"-tecken) är strängkonkatenator, dvs slår ihop två strängar.

Funktionen suspend är en speciellt funktion som håller reda på var någonstans i genereringen man är. Denna typ av funktioner kallas även för generator eller closure.

Ovanstående program skapar 648 namnvarianter, varav samtliga är med i listan på den ovan nämnda sajten. Programmet pattern_generation.icn är en utbyggd version som visar lite mer information etc. Här är output från detta program.

Not: skulle vi inte haft restriktionen att för-/efternamn inte får börja på samma bokstav skulle programmet bli ännu enklare:


procedure main()
   every x:= (HM2() || " " || HM2()) do write(x)
end

procedure HM2()
  suspend !"HM" || !"ea" || !["nk","n", "nn"] || !["ing","ell","all"]
end

Detta program genererar 1298 namn.


Lite mer om Icon
Icon har många andra trevliga features, framförallt ett mycket kraftfullt system för pattern matching (influerat av SNOBOL) som är helt olikt den numera förhärskande metoden med reguljära uttryck.

Förutom ovan nämnda sajter finns det några PDF-böcker om Icon/Unicon som rekommenderas:

Ralph E. Griswold, Madge T. Griswold: The Icon Programming Language (3rd ed)
Clinton Jeffery, Shamim Mohamed, Ray Pereda, Robert Parlett: Programming with Unicon (eventuellt en blivande O'Reilly-bok).
Thomas W Christopher: Icon Programming Language Handbook


För mer om reguljär uttryck (regular expressions) se t.ex. blogganteckningen Reguljära uttryck.

Posted by hakank at 01:39 EM Posted to Reguljära uttryck etc | Språk

januari 18, 2004

Mer om reguljära uttryck (i Perl)

I Maintaining Regular Expressions (perl.com) beskriver Andy Mackey sin Perl-modul Regexp::DeferredExecution.

Modulen beskrivs på följande sätt: This module provides the ability to include embedded Perl code within regular expressions via the usual (?{}) construct, but defer the execution of that code until the end of a successful pattern match.

Andra moduler som refereras i artikeln:
Regexp::Fields
Regexp::English


Se även Mackeys artiklarO'Reilly Network.

Posted by hakank at 08:15 FM Posted to Reguljära uttryck etc

november 27, 2003

Reguljära uttryck i Java

I ONJava.com: Regular Expressions in J2SE berättas hur man arbetar med reguljära uttryck i Java. Rekommenderad läsning för mindre vana regexare.

Se även min anteckning Reguljära uttryck samt MakeRegex som skapar ett enkelt reguljärt uttryck givet en lista av ord. Detta program finns även som applet.

Posted by hakank at 05:33 EM Posted to Reguljära uttryck etc

augusti 10, 2003

Reguljära uttryck

Sedan många år har jag varit fascinerad av reguljära uttryck (regular expressions, regex, regexp, nedan förkortat "RE"). Det är ett kärnfullt sätt att söka i texter med ett fåtal operatorer och "funktioner", och - efter en viss inkörningstid - känns det nog som om man inte kan leva utan dem.

Förutom grep-familjen och andra Unix-utiliteter har de flesta programspråk numera någon variant av RE, antingen direkt i språket (som Perl och Ruby) eller som standardbibliotek (som Java och Python) eller som tredjepartsbibliotek (de flesta andra språken). Personligen är jag väldigt förtjust i Perl och Rubys RE-operatorer.

Anledningen att jag skriver om detta just nu är att jag hittade sajten
Regular expression Library som är en kommunitet där man kan läsa, skriva och kommentera RE.

En bra finess är att det finns både "Sample Matches" och "Sample Non-Matches", dvs exempel både på textsträngar som matchar ett RE-uttryck och sådana som inte matchar. Det finns även en sida där man kan testa ett speciellt RE (valet "Test" på en RE-sida). Sajten har också ett ratingsystem som möjligen kan bli användbar.

Det stora poängen med sajten är nog mer att få inspiration än att hitta den korrekta lösningen på sitt specifika problem, vilket väl egentligen alltid är fallet med kokboks-lösningar. T.ex. är det lite vanskligt, kanske till och med farligt beroende på applikationen, att tro att man matchar precis alla möjliga varianter av epost-adresser (From:-raden i ett mail) med de uppräkningar som finns i kategorin email. I många fall är de naturligtvis användbara. Så var varsam!

Sajten kan bli riktigt intressant om den får hålla på ett tag till.


Här är lite länkar till vidareinformation om reguljära uttryck.


När jag började bli riktigt fast i RE-träsket skrev jag MakeRegex, som tar en lista med ord och gör om till ett relativt enkelt RE. Programmet har många begränsningar, men jag (liksom några andra) har faktiskt haft riktig nytta av det några gånger. Man kan leka med det både som CGI-program och som Java-applet. En lite mer useless variant är MakeRegex web som skapar ett RE för en webbsida.

Posted by hakank at 02:11 EM Posted to Reguljära uttryck etc