Tokens, Attributes, and pseudo XML parsing in Erlang
I have a very specific need, and I have this wild idea I can solve it with Erlang. Grosso modo, the need is that I have to parse a huge XML file, but I mean something fiercely huge. I haven’t seen it yet – my client has it – but even my very very specific, can break if you move a comma, I am reading this file as plain text parser, which I wrote for this client and this file format, takes forever to parse the file. Attempts to read that file, or similar, albeit a tad smaller ones, with expat et altri was entertaining but fruitless.
So I broke out the big guns. I have three computers at home – well four, but my wife’s old TiBook 15″ is sick – and will prolly have one or two more soon, thanks to recent/current contract work. And one at least will be dual core, or better* so it should be interesting.
* I haven’t decided yet whether to buy a double core or better G5 – since most of my commercial apps are PPC, and OSS stuff can be recompiled and sped up with -mcpu=g5 – or to buy an Intel. We’ll see.
Those two of you who read my posts on Erlang and survived know that I have been playing with concurrency, distributed computing [ridiculously easy to set up in Erlang, but I suspect there are pitfalls lurking right across the corner to bite me…], looping through lists and tuples [of distributed nodes, wink wink], and complaining about string manipulations [for all I know Erlang has a superb set of string manips, but people on #erlang agreed that it’s so so…]. Now, I *need* decent string manips if I am to fake-parse XML. So far, I can start nodes on remote machines, read lines from a file and send these lines to the nodes in a round-robin way, to be processed. Meaning, to obtain the content of the XML – in this case the attributes – and store them somewhere. The “store somewhere” part, I’ll leave for later, we can’t win all battles in one day. Just the word mnesia makes me shiver… For the time being, the parsed output will go to the node’s dictionary. Good enough.
Now, I started working on this with another XML file that has a similar format: the opml file produced by Technorati. It looks like this:
<?xml version="1.0" encoding="UTF-8"?>
<!– OPML generated by Technorati Blog Finder –>
<opml version="1.0">
<head>
<ownerName>Technorati</ownerName>
<title>5 blogs tagged Erlang sorted by authority</title>
</head>
<body>
<outline text="3pBlog Mickaël Rémond Performance, Process, P… " description="Mickael Remond’s thoughts on cluster, robust, scalable and distributed computing" htmlUrl="http://www.3pblog.net" xmlUrl="http://www.3pblog.net/rss.php" type="rss"/>
<outline text="Life’s too short to brag about microcosm a… " htmlUrl="http://sungnyemun.org/wordpress" xmlUrl="http://sungnyemun.org/wordpress/wp-rss2.php" type="rss"/>
[…]
</body>
</opml>
The idea is to extract the 5 attributes – not all five may be present, so it’s actually a good idea to preset the dictionary with the five keys and empty values – and return a tuple, list, dictionary, whatever. Read the file until you hit <body> and then start reading lines until </body>. Ok, can do. Then, for each line, I read the “header” [<outline ], and then hope for the best and pray that the tag/attribute pairs are properly formatted – no reason to doubt, they’re machine-produced, right? So I need a function to retrieve the tag [which I called token], and then the attribute. This until I hit “/>”, the end of the line, as far as the “parser” is concerned. I know, many things could break, but if the format is consistent… we should be safe!
Here goes:
-compile(export_all).
doit(S) -> % that’s the function we’ll call
% reset the dictionary
put(text,""),
put(type,""),
put(htmlUrl,""),
put(description,""),
put(xmlUrl,""),
proceed(S).
proceed("/>") -> % This is the closing tag, we’re done.
{{text, get(text)}, {type, get(type)}, {htmlUrl, get(htmlUrl)}, {description, get(description)}, {xmlUrl, get(xmlUrl)}};
proceed([$< |T]) -> % opening tag, read the header
{S1,Head}=extract_header(T),
proceed(S1);
proceed([32|T]) ->
proceed(T);
proceed(S1) -> % any other possibility
{S2,Tk}=extract_token(S1),
{S3,Attr}=extract_attribute(S2),
Atom=list_to_atom(Tk),
put(Atom,Attr),
proceed(S3).
extract_header(L) ->
extract_header(L,[],0).
% the last argument, 0 and then 1 is just a state marker
extract_header([H|T],Acc,0) ->
case H of
32 -> extract_header(T,Acc,1);
Other -> extract_header(T,[H,Acc],0)
end;
extract_header([H|T],Acc,1) ->
case lists:member(H, "qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM1234567890 -_") of
true -> {[H|T],lists:reverse(lists:flatten(Acc))};
% Return header + remainder
Other -> extract_header(T,Acc,1)
end.
extract_token(L) ->
extract_token(L,[]).
extract_token([H|T],Acc) ->
case lists:member(H, "qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM1234567890 -_") of
true ->
case Acc of
[] -> extract_token(T,H);
Other -> extract_token(T,[H,Acc])
end;
false -> {[H|T],lists:reverse(lists:flatten(Acc))}
end;
extract_token([],Acc) ->
{">",lists:reverse(lists:flatten(Acc))}.
extract_attribute(L) ->
extract_attribute(L,[],0).
extract_attribute([H|T],Acc,0) ->
case H of
34 -> extract_attribute(T,Acc,1); % Open "
Other -> extract_attribute(T,Acc,0)
end;
extract_attribute([H|T],Acc,1) ->
% " open
case H of
34 -> {T,lists:reverse(lists:flatten(Acc))}; % Close ". Return Acc
Other -> extract_attribute(T,[H,Acc],1)
end.
70> S2="<outline text=\"3pBlog Micka\303\253l R\303\251mond Performance, Process, P… \" description=\"Mickael Remond’s thoughts on cluster, robust, scalable and distributed computing\" htmlUrl=\"http://www.3pblog.net\" xmlUrl=\"http://www.3pblog.net/rss.php\" type=\"rss\"/>".
71> extract:doit(S2).
{{text,"3pBlog Micka\303\253l R\303\251mond Performance, Process, P… "},
{type,"rss"},
{htmlUrl,"http://www.3pblog.net"},
{description,"Mickael Remond’s thoughts on cluster, robust, scalable and distributed computing"},
{xmlUrl,"http://www.3pblog.net/rss.php"}}
Sweet, no? 
I am sure this is clumsy. But.It.Works. Now on to bring all the pieces together… And learn about mnesia and stuff.
March 23rd, 2006 at 5:22 am
When are you going to post the original source code and not that decompiled ugly thing?
March 24th, 2006 at 7:39 am
dda, why do you insists in doing lexical analysis and parsing in a high-level language such as Erlang? These tasks, especially scanning, must be carried out very efficiently by a low-level library or third-party tool, like GNU Flex. In other words: stick with C, Perl, Python, Ruby etc. for such intensive I/O and string processing. Distribution, nodes et tutti quanti won’t help a bit.
Functional languages are very powerful for doing symbolic computations, in particular developping compilers but NOT their front-end. In the same vein, do not expect good results by using Erlang for doing floating-point intensive computations.
March 24th, 2006 at 8:33 am
Une idee est d’extraire du fichier XML des parties correspondant a des freres dans l’arbre, que tu pourrais ensuite traiter separement. S’ils sont encore trop gros, re-itou. Evidemment, si ton document est un arbre degenere (une liste), c’est inutile et les regexp sont tes amies (puisque tu as affaire a un mot appartenant a un langage regulier).
D’abord il faudrait savoir a quelle profondeur a partir de la racine du document commencent les sous-arbres avec au moins un frere. Une fois que tu sais, tu retiens ce niveau d’indentation.
Puisque le fichier XML est produit automatiquement, est-ce que tu peux compter sur l’indentation?
Ensuite, tu peux lire le fichier ligne par ligne (pas en Erlang) tout en gardant le compte du nombre d’octet lus depuis le dernier point (le premier sous-arbre avec des freres est le premier point) et, en debut de ligne, mesure l’indentation. Si cette indentation est la meme que celle du dernier point, tu sais que tu as lu un frere et tu fais un coup de split, par exemple.
Si ca t’amuse, ensuite tu peux distribuer l’analyse lexicale (tokenisation), mais faut voir si le temps de transfert des sous-arbres n’est pas plus important que l’analyse elle-meme.
En fait, j’ai pour projet de m’attaquer a ce type de probleme moi-meme dans les semaines qui viennent, a partir d’un autre langage fonctionnel (Objective Caml) — pour les actions semantiques, pas pour l’analyse lexicale et syntaxique elle-meme.
Au fait, tu as essaye XSLT? La plus part des implantations chargent le fichier d’entree en memoire, d’apres ce que j’ai lu, donc c’est pas bon. Mais peut-etre que XQuery fait mieux, puisqu’il y a deux modes: ouverture d’un fichier XML et flux d’elements XML a partir d’une BD. Dans ce dernier cas, il faudrait que le XML soit deja dans une BD, ce qui revient a se mordre la queue — ouille — dans ton cas. Hum.
March 24th, 2006 at 12:02 pm
Christian, merci pour ces deux commentaires. En fait, j’ai déjà un parseur pour ce fichier, qui est – généralement – ultra rapide, et qui fait grosso modo comme tu le suggères dans ton second commentaire. Et les résultats sont très bons, pour des fichiers de taille normale [jusque vers 9~10,000 enregistrements XML complexes]. Mais comme il y a toujours des cas uniques/spéciaux, mon client a des utilisateurs avec des fichiers beaucoup plus gros que ce que l’on attendait, dont l’un avec plus de 35,000 enregistrements, je crois.
Et là ça devient sérieusement lourd. Et le Mac/PC nous fait souvent un caca nerveux… D’où l’idée de confier la tâche à Erlang, pour voir. D’abord, ça fait un moment que je voulais apprendre Erlang, et c’est un prétexte aussi bon qu’un autre…
Pour ce qui est de l’indentation, elle est uniforme, mais je ne m’en sers pas, car j’ai trouvé mieux : la structure du fichier est telle qu’une fois que je suis dans le bon nœud, il me suffit de tester la ligne sans whitespace en conjonction avec un marqueur de profondeur : si le marqueur est à zéro, il y a quatre possibilités [fin du nœud, début d’un sous-nœud, fin d’un sous-nœud, ou alors c’est… un truc dont j’ai pas besoin !]; et si le marqueur est à 1, c’est une partie d’un élément complexe. Donc ça, ça va. Si je suis en profondeur 1, je crée un nouveau process de tokenisation avec cette ligne en paramètre, et je passe à la ligne suivante. Si c’est une fin de sous-nœud, je vide le dictionaire dans un fichier en SQL [et depuis ce matin trèèèèèès tôt, dans une table Mnesia, ouch! trop lent] et je le remets à zéro.
Donc la conclusion – pour le moment – est not bad, même si la distribution ne m’a rien apporté, pour le moment [j’attends de voir avec les vrais fichiers]. La concurrence, par contre, se montre redoutable. Après tout, pour parser 2,020 enregistrements, il m’a fallu lire près de 60,000 lignes et créer autant de processes séparés [même s’il n’y en a jamais 60,000 qui tournent en même temps…]. Et tout ça en 3 secondes. Comme disait Garcimore, “Pas mal…”.
Maintenant, il me faudrait toujours produire une base sqlite, et comme sqlite n’autorise pas les accès concurrents, les développeurs d’Erlang ne semblent pas très intéressés. Moi je m’en tape un peu, puisque mes écritures disque sont centralisées sur un seul processus. Mais bon…
March 24th, 2006 at 6:14 pm
Tout ca me fait penser qu’on a bien de la chance d’avoir des epouses coreennes, qui acceptent qu’on soit en train de hacker tot le matin, comme moi, la, a 1 heure du mat dans le lit:-)
Donc, tu es satisfait du parseur, si j’ai bien compris?
Sinon, je me demande si on ne pourrait pas directement decouper le fichier originel en portions de taille arbitraire mais relativement petite (d’une taille que tu sais etre celle d’un fichier rapidement traite par ton parseur), avec split, par exemple. Puis tu distribue ces morceaux a differents processus qui en font l’analyse lexico-syntaxique separement. Le truc marrant c’est que ce ne sont pas forcement des sous-arbres XML complets en general, mais des morceaux (coupes a la hache!). Il faudrait decrire le langage de ces fragments et ecrire un petit protocole pour syncroniser les differents processus d’analyse pour produire les fichiers SQL (ou autre) correspondant aux sous-arbres complets…
Je suis un peu fatigue, la, pour poursuivre, et puis tu sembles deja avoir resolu le probleme.
March 24th, 2006 at 6:43 pm
Satisfait par le parseur, non. Mais statisfait de mes premiers efforts. Des essais aujourd’hui ont donné des résultats intéressants mais toujours un tantisoit améliorables : 33 secondes pour 22,000+ éléments complexes. Mais je pense que l’on peut faire mieux. J’ai déjà gagné un peu de temps en débroussaillant le code… La version 11 d’OTP/Erlang introduira [peut-être] le multi-core. Me faut une machine qui va bien, œuf corse, mais d’après Joe Armstrong, ça devrait bien booster…
Comme toi je pense que l’on peut jouer sur la granularité, peut-être passer des plus gros bouts de texte à traiter. Je pensais passer un nœud entier – comme ça on a une unité bien nette à bidouiller. Ça laisse du travail pour une version 2
March 24th, 2006 at 6:50 pm
Et tu as raison pour nos épouses coréennes… Pour la raison indiquée et bien d’autres