Aquila project

Latest published version:
http://mozilla.hoa-project.net/Aquila/literature/html/
Previous versions:
-
Editor:
Ivan Enderlin, Mozilla's intern, developper of Hoa Framework

Abstract

The Aquila project aims to be a new experimental perform find system for Firefox.

This is the ideas manual, i.e. all ideas, sketches, early drafts etc., are written here.

Table of contents

  1. mark element: prestissimo
    1. Needs and usages
    2. Gecko implementation status
  2. Core: allegro
    1. AquilaUtil, core utility
      1. Get the current window
      2. Get the current document
    2. AquilaInterface, interface manager
    3. AquilaFinder, finder
      1. Find a word
      2. Move in matches
    4. Prelude and bootstrap
      1. XPCOM constants and log
      2. Bootstrap
  3. User experience
    1. Matching search
      1. Pattern matching algorithms
        1. In extenso search
        2. Regular expressions
        3. Approximated search
      2. Phonetic search
    2. Relevance of search results
      1. Weight and distance
      2. Group and section
      3. Euclidean distance
    3. Smartcase
  4. User interface
    1. Findbar
      1. Layout of the finbar
      2. Central search
      3. Next and previous
      4. Matches arity
    2. Results listings
      1. List of excerpts
      2. List of sections or groups
      3. List of excerpts grouped by sections
    3. Matches localizing…
      1. …with a list
      2. …with a scrollbar
        1. Place points
        2. Bubbles and moving


Introduction: preludio

Presentation

This section is non-normative.

The Aquila project aims to be a new experimental perform find system for Firefox, distributed as a Firefox extension (downloadable as a .xpi file). Just type Accel + Shift + F to open the sidebar.

Background

This section is non-normative.

The current find system in Firefox dates from the time of Netscape. No new feature was added since this time. Nevertheless, user experience and user interface are increasing all the days: Web documents are longer, denser and contain more informations than ever.

No research about a new way of finding informations on a Web document has been recently exposed. At present, the majority of browsers uses a simple findbar (accessibles via Accel + F) but it could be the wrong way. For example, if a Web document is heigher than the window, user is not aware if some results was found somewhere else in the document.

The current system is incremental (it means: previous, next) and not very visual. The Aquila project attempts to rectify this, while proposing many experimentals features.

Audience

This section is non-normative.

This document is intended for all people that are interesting by the project, have ideas, fancies etc.

Yet, this document is probably not suited to readers who do not already have at least a passing familiarity with Web technologies, users experiences or users interfaces.

Scope

This section is non-normative.

This document provides all ideas, sketches, early drafts etc., comes with a semantic tour using new HTML 5 tags.

mark element: prestissimo

Needs and usages

HTML 5 introduces a new HTML semantic element: mark.

The HTML 5 specification describes it like:

The mark element represents a run of text in one document marked of highlighted for reference purposes, due to its relevance in another context. When used in a quotation or other block of text referred to from the prose, it indicates a highlight that was not originally present but which has been added to bring the reader's attention to a part of the text that might not have been considered important by the original author when the block was originally written, but which is now under previously unexpected scrutiny. When used in the main prose of a document, it indicates a part of the document that has been highlighted due to its likely relevance to the user's current activity.

This element meets the needs of a search. Indeed, the scope of the mark element is to mark found matches.

For example, 42 words of a lipsum:

Lorem ipsum dolor sit amet, consectetur adipiscing elit. Proin egestas sodales nulla id imperdiet. Aenean facilisis varius nulla, in feugiat arcu consequat vel. Suspendisse potenti. Mauris vitae nisi orci. Praesent tincidunt consectetur condimentum. In laoreet sodales nibh id facilisis. Donec porta faucibus.

We search the in text, then:

Lorem ipsum dolor sit amet, consectetur adipisc<mark>in</mark>g elit. Pro<mark>in</mark> egestas sodales nulla id imperdiet. Aenean facilisis varius nulla, <mark>in</mark> feugiat arcu consequat vel. Suspendisse potenti. Mauris vitae nisi orci. Praesent t<mark>in</mark>cidunt consectetur condimentum. In laoreet sodales nibh id facilisis. Donec porta faucibus.

Gecko implementation status

A bug is currently open on Bugzilla: Bug 485377, Implement HTML5's mark tag.

An early draft was proposed but it is not as relevant as we hoped it would be. It calls into question the general semantic tag declaration in Gecko; typically all elements that are span like. We are precisely focused on this point.

We are working on a new patch.

Core: allegro

We try to describe the Aquila core.

AquilaUtil, core utility

The prototype AquilaUtil allows user to get some usefull datas, like object, values, context etc.

Get the current browser

A first getter is browser that returns the current browser — through XPCOM —. Thus:

var aquilaUtil = new AquilaUtil();
var browser    = aquilaUtil.browser;

Get the current window

A first function is getCurrentWindow that returns the current selected window. It takes care about the selected tab. Thus:

var aquilaUtil    = new AquilaUtil();
var currentWindow = aquilaUtil.getCurrentWindow();

Get the current document

We also have the getCurrentDocument that returns the current selected document. Like its twin, it takes care about the selected tab. Thus:

var aquilaUtil      = new AquilaUtil();
var currentDocument = aquilaUtil.getCurrentDocument();

AquilaInterface, interface manager

AquilaFinder, finder

Find a word

Move in matches

Prelude and bootstrap

XPCOM constants and log

The prelude defines two usefull constants: Cc and Ci, respectively to get the Components.classes and Components.interfaces values.

The log function is added to help you to debug your application, making test etc. It is easily hackable. Example given:

log("= Ready to go!");

Bootstrap

The global variable aquila is declared on the top of the application and contains all aquila's prototypes (previously saw), like AquilaUtil, AquilaInterface and AquilaFinder, through a simple associative array. Thus:

aquila.util.getCurrentWindow(); // will return the current window.
aquila.finder.find();           // will find a word in the current document.
// …

User experience

This section describes the manner whose we should search elements to answer as better as possible to the user's need. We do not focus on the user interface, i.e. the way to present the result, but instead the manner whose we should find the result.

Frist, we start with a presentation of several ways to find matches from a sequence, next, we will focus on the more relevant manner to gather round matches, in order to create groups to get a better relevance in the result.

This part aims to find textually which match better to what user search.

Le but de cette partie est de trouver textuellement ce qui correspond au mieux à ce que l'utilisateur cherche. On n'a pas encore réellement cette notion de pertinence. On cherche à trouver toutes les occurences qui se rapproches au mieux de ce que souhaite l'utilisateur. Soit on cherche toutes les occurences in extenso, soit on cherche à l'aide d'expression régulières, soit on cherche à quelques différences près, soit toutes les occurences qui ont la même prononciation.

Une fois toute les occurences trouvées, cela nous constituera une première base. Toutefois, les occurences seront ordonnées selon l'ordre naturel du document. Cet ordre n'est pas nécessairement le plus pertinent. Cette liste d'occurences va donc être remaniée pour être triée de façon plus pertinente.

Pattern matching algorithms

On peut constater deux manières de chercher des occurences dans un texte. La première — présentée ici — est textuelle. La seconde — présentée dans la section suivante — est phonétique.

Parmis ces techniques textuelles, on peut en considérer trois : une recherche triviale, ou in extenso, une recherche par expressions régulières ou enfin une recherche approchée.

Une première approche triviale serait de chercher une séquence dans un document in extenso, c'est à dire on cherche la séquence complète, sans différence, sans se soucier du sens de la séquence etc.

C'est de cette façon que procède Firefox actuellement.

De cette manière, on récupère tous les éléments correspondants à notre recherche. Tous les éléments seront identiques (à une sensibilité de casse près).

Considere this text as example:

Here is simply a simple example, very simple!

Search simpl will match:

Here is <mark>simpl</mark>y a <mark>simpl</mark>e example, very <mark>simpl</mark>e!

Une manière pertinente de chercher une occurence serait d'utiliser un modèle vecteur-binaire.

Si on utilise un système basé sur les expressions régulières, il suffit d'échapper tous les caractères spéciaux réservés aux expressions.

Regular expressions

Les expressions régulières sont un mécanisme puissant exprimant la théorie des langages réguliers.

Il existe plusieurs moteurs, plus ou moins puissants, plus ou moins rapides, plus ou moins expressifs etc. Parmis la multitude de moteurs, on conseille d'utiliser le moteur PCRE, pour Perl Compatible Regular Expressions. Une implémentation en C existe et est disponible sur le site PCRE.org.

Considere this text as example:

Here is simply a simple example, very simple but not simplistic about PCRE assertions that actually are not that simple!

Search simpl.*\b will match:

Here is <mark>simply</mark> a <mark>simple</mark> example, very <mark>simple</mark> but not <mark>simplistic</mark> about PCRE assertions that actually are not that <mark>simple</mark>!

Les recherches approchées peuvent être réalisées à l'aide d'expression régulières mais au détriment d'une syntaxe lisible et d'une rapidité à l'exécution.

Il existe des algorithmes spécialés dans la reconnaissance de séquences approchées, notamment dans la génétique pour la recherche de chaînes ADN.

Un exemple significatif :

On cherche GATAA dans CAGATAAGAGAA avec au plus une différence :

Ce type de recherche permet de trouver des occurences même si l'utilisateur fait des fautes de frappes. Ce n'est pas le seul cas intéressant car il peut trouver des mots avec un sens légèrement différent, ou avec une conjugaison, un accord, une orthographe légèrement différente.

Une manière pertinente de déployer une telle recherche serait d'utiliser l'algorithme de recherche par motifs approchés, avec différences, basé le principe de la monotonie sur les diagonales.

Une autre manière plus simple serait d'utiliser la distance de Levenshtein, est de sélectionner tous les mots ayant une distance inférieure à un n donné.

Si la distance de Levenshtein n'est toujours pas suffisante, on peut encore s'arrêter sur la distance de Hamming, qui se veut plus généraliste.

Le principe des algorithmes phonétique est d'effectuer un rapprochement entre les mots à partir de leur prononciation.

Le problème avec ces algorithmes est qu'ils ne fonctionnement que pour une seule langue, et généralement l'anglais.

On notera toutefois :

Attention, penser aux phonèmes.

A priori, on aurait plus tendance à s'intéresser à l'algorithme Double Metaphone, qui semble plus pertinent et couvre plus de langues.

Le nombre de langues supporté est un problème pour le déploiement sur Firefox car le logiciel existe en 70 langues. Il faut que l'algorithme utilisé comprenne autant de langues.

Relevance of search results

La section précédente présentait les manières dont trouver des résultats, comprendre des occurences, dans un document. Cette section continue le travail en essayant de trier les résultats afin de proposer une plus grande pertinence.

Weight and distance

Une première manière de trier la liste des résultats est d'affecter un poids à chaque résultat. Les poids les plus lourds seront les plus pertinents, et les poids les plus faibles, les moins pertinents.

On propose plusieurs idées pour attribuer un poids à un résultat.

Group and section

Une approche intéressante serait de ne pas présenter les résultats mais les groupes ou sections du document qui contiennent le plus de résultat. Par exemple, si une section contient trois résultats et qu'une autre n'en contient que deux, la première aura un poids plus fort, et donc sera plus pertinente.

On va raisonner par section pour la suite de cette partie.

Les sections sont basées sur les balises h1 à h6 de l'HTML 5. On ne considère par les niveaux d'imbrications (h2 nécessairement dans un h1), ni les regroupements (avec les balises section ou hgroup). Pour l'instant, les résultats trouvés en dehors des niveaux de section sont ignorés (avant que l'on ait trouvé une façon correcte de gérer ce cas).

On se base sur cet exemple :

<article>
  <hgroup>
    <h1>heading 1</h1>
    <p>dummy value</p>

    <h2>heading 2</h2>
    <p>dummy & dummy</p>
  </hgroup>

  <p>A paragraph with a dummy value.</p>

  <section>
    <h1>heading 1'</h1>
    <p>dummy value</p>
  </section>

  <section>
    <h1>dummy 1''</h1>
    <p>dummy dummy dummy & so on!</p>
  </section>
</article>

Here is a “list-view” (or a “DOM-view”), with matches number:

On tente un premier tri décroissant : 4 (E), 2 (B), 1 (A), 1 (C) et 1 (D). Le paragraphe (C) est en dehors des sections, donc on ne le comptabilise pas. Ce qui revient à : 4 (E), 2 (B), 1 (A) et 1 (D).

Dans notre exemple, on remarque que la pertinence n'est pas complète. En effet, il y a une égalité entre (A) et (D). Pour obtenir une pertinence complète, il est nécessaire de les départager. C'est là que la notion de distance intervient.

On va naïvement commencer par une distance DOM. Par exemple, dans notre cas, (D) est plus proche de (E) (la section la plus pertinente) que ne l'est (A). Donc on suppose que (D) sera plus pertinent que (A).

Ainsi, le résultat final sera : 4 (E), 2 (B), 1 (D) et 1 (A).

S'il existe encore une égalité à ce niveau, on peut supposer que l'ordre n'ajoutera pas une plus grande pertinence, et on pourra passer le tri, c'est à dire qu'on le laissera tel qu'il est.

Penser à utiliser la géométrie hyperbolique, et surtout des hypertrees. On peut définir des hypertrees à 3 ou 4 niveaux, et on utilise les niveaux les plus petites (proches du centre) pour départager les égalités lors du premier tri.

Euclidean distance

Smartcase

Case sensitivity is generally putted right by a checkbox. However, we may have a “smart” sensitivity handling.

If all characters are in lowercase, we can suppose that the case is not important, and thus the sensitivity is null. If at least one character is in uppercase, thus the case will be sensitive.

Let the text:

Aquila project: aquila means eagle in latin.

We search Aquila (it is case sensitive):

<mark>Aquila</mark> project: aquila means eagle in latin.

We search aquila (it is case unsensitive):

<mark>Aquila</mark> project: <mark>aquila</mark> means eagle in latin.

User interface

L'expérience utilisateur décrit cette fois la façon de présenter les résultats, la façon dont l'utilisateur va interagir avec son système de recherche.

Findbar

La bare de recherche doit être suffisant grande pour pouvoir tout afficher, ou suffisament bien placée pour ouvrir des éléments graphiques sans gêner l'utilisateur. Elle doit permettre également de placer tous les boutons nécessaires.

Layout of the findbar

La barre de recherche peut-être située à plusieurs endroits mais on propose : soit horizontalement en bas de la fenêtre, soit verticalement en sidebar.

Si on choisit une position plutôt qu'une autre, ce sera une question de compromis. En effet, une sidebar permet d'afficher plus d'éléments mais prend plus de place. Une barre horizontal va prendre moins de place mais les divers listes de résultats devront être accessibles via des boutons (on ne considère pas encore les points sur les scrollbars).

Il faudrait utiliser les recherches précédemment effectuées sur d'autres sites, sur d'autres moteurs de recherches ou même sur le système d'exploitation (on pense notamment à Spotlight pour Mac OS X).

Next and previous

Il est nécessaire de pouvoir se déplacer vers l'arrière ou vers l'avant dans le document afin de passer d'une occurence trouvée à une autre. On peut soit mettre du texte, soit mettre des flèches. Les flèches sont préférables car plus visuelles et plus petites (gain de place).

L'appuye systématique de la touche Enter va forcer le passage à l'occurence suivante.

Si on utilise des listes, le fait de changer d'élément dans la liste va changer l'occurence courante. Si on utilise des points dans la barre de défilements pour naviguer, le fait de sélectionner un point va changer l'élément courant. Etc. Si on ré-utilise les boutons pour se déplacer, on doit redémarrer selon le point courant, attention donc à bien mémoriser ça. L'expérience utilisateur ne sera que meilleure.

Matches arity

Une fonctionnalité intéressante pour l'utilisateur est de lui signaler combien d'occurences ont été trouvées dans le document.

Cette information peut-être sous plusieurs formes : soit on lui indique seulement si au moins une occurence a été trouvée ou pas, soit on lui indique le nombre exact d'occurences trouvées, soit on peut retranscrire ces informations sous forme de couleurs. Toutefois, si on utilise des couleurs, on risque de rendre l'information moins précise.

Results listings

On explique comment présenter les résultats.

List of excerpts

Une première liste serait la liste de toutes les occurences trouvées, avec les quelques mots précédents et suivants afin de créer un extrait.

List of sections or groups

Une seconde liste serait la même que la première mais avec les occurences regroupées en section. Ainsi, on ne verrait que le nom des sections avec en première colonne une barre de progression statique qui indique la pertinence de la section.

List of excerpts grouped by sections

On peut également avoir notre liste d'extraits mais regrouper (folded) sous des sections.

Matches localizing…

Les systèmes de recherche actuels fournissent réellement peu d'informations. Une information qui manque cruellement est la position des occurences dans le document. Sans bouger son document dans sa fenêtre, l'utilisateur doit être capable de repérer la position globale de toutes les occurences. Par exemple, savoir s'il y a des éléments plus bas dans la page.

…with a list

Dans le cas d'une liste, on peut assombrir tous les éléments qui sont non-visibles, i.e. en dehors de la fenêtre. Plus l'élément est sombre et plus il est loin de la position courante de la fenêtre. Cette distance se calcule bien sûr en pixel.

…with a scrollbar

Si on souhaite connaître visuellement la position de toutes les occurences dans la page, on peut soit réduire la page pour la voir en entier, soit utiliser les barres de défilement (on prendra l'exemple de la barre de défilement vertical, mais un raisonnement strictement analogue peut être effectué sur la barre de défilement horizontal).

Place points

En effet, on peut placer des points sur la barre de défilement (ou à côté) en fonction de la position des occurences dans la page. Par exemple, si une occurence est trouvée tout en bas de la page, soit à 87 % de la hauteur, on trouvera un point à 87 % de hauteur sur la barre de défilement.

Bubbles and moving

L'information sur la position des occurences est plus rapide à interpréter par l'utilisateur car visuelle. Toutefois, les points doivent avoir d'autres utilités.

Lorsque l'on place son curseur sur un point, on pourrait avoir une bulle contenant un extrait de la page autour de l'occurence. Cela permet à l'utilisateur d'avoir un contexte visuelle et textuelle de l'occurence.

On peut ensuite très bien imaginer qu'un simple clique sur le point va faire glisser la fenêtre jusqu'à l'occurence.

Le point courant peut avoir un style particulier pour être différencier des autres. Le même raisonement peut-être effectuer sur un groupe de points, i.e. tous les points représentant des occurences visibles auraient un style différent (par exemple, moins visible).

Document state when searching

Page preview

Highlight and darken

Smooth transition

Focus the current match


List of excerpts

List of relevant sections

Fit the page

Bubbled scrollbar

Smooth transition when jumping

Le déplacement dans une page s'effectue toujours par accout. On pourrait imaginer un déplacement plus doux.

En effet, un déplacement accompagné d'une transition permet à l'utilisateur se repérer dans son document, i.e. il sait où il s'est déplacé.

Note technique, on conseille d'appliquer une transition quadratique du style ease out.

Focus the current matched element

L'occurence courante devrait obtenir le focus. Par exemple, si c'est un lien, il devrait être pré-sélectionner, si c'est un champ de texte, le curseur devrait être positionné au bon endroit dedans, si c'est un texte, on devrait avoir l'occurence qui sélectionnée. Ça pourrait être utile.

Highlight viewable matches in a list

Si on doit présenter le résultat sous forme de liste, on peut griser toutes les occurences qui ne sont pas dans la fenêtre pour signifier qu'elles sont invisibles à l'utilisateur. Cela permet d'avoir une notion de position pour l'utilisateur. Bien sûr, cette technique ne sera pas applicable si on utilise une liste avec un regroupement par pertinence, mais uniquement si on utilise une liste avec des extraits.

Darken the document except matches

Pour afficher les occurences trouvées dans le document, on peut griser l'ensemble du document — i.e. l'assombrir — et faire ressortir — i.e. accentuer — les occurences. Un peu comme Safari le propose.

Appendix

Search with an approximated patterns, with differences

Here is a algorithm of a search with an approximated pattern, with differences, based upon the diagonal monotony, in PHP.

<?php

header('content-type: text/plain');

/*  Search by approximated patterns, with differences */
/*     based upon the principle diagonal monotony.    */


function approximatePatternMatchingWithDifferences ( $x, $y, $k ) {

    $m      = strlen($x);
    $n      = strlen($y);
    $offset = array();

    for($d = -1; $d <= ($n-$m+$k+1); $d++)
        $L[-1][$d] = -2;

    for($q = 0; $q <= ($k-1); $q++) {

        $L[$q][-$q-1] = $q-1;
        $L[$q][-$q-2] = $q-1;
    }

    for($q = 0; $q <= $k; $q++) {

        for($d = -$q; $d <= ($n-$m+$k-$q); $d++) {

            $l         = max($L[$q-1][$d-1],
                             $L[$q-1][$d]  +1,
                             $L[$q-1][$d+1]+1);
            $l         = min($l, $m-1);
            $a         = substr($x, $l+1   , -($l)   +($m-1));
            $b         = substr($y, $d+$l+1, -($d+$l)+($n-1));
            $L[$q][$d] = $l+lcp($a, $b);

            if(   $L[$q][$d]    == $m-1
               || $d+$L[$q][$d] == $n-1) {
                $j            = $m+$d;
                $i            = $j-$m >= 0 ? $j-$m : 0;
                $offset[$q][] = array('i' => $i, 'j' => $j);
            }
        }
    }

    return $offset;
}

function lcp ( $x, $y ) {

    $max = min(strlen($x), strlen($y));
    $i   = 0;

    while($i < $max && $x{$i} == $y{$i})
        $i++;

    return $i;
}

$x      = 'GATAA';
$y      = 'CAGATAAGAGAA';
$k      = 1;
$search = approximatePatternMatchingWithDifferences($x, $y, $k);

$n      = count($search);
echo 'Try to match ' . $x . ' in ' . $y . ' with at most ' . $k . ' difference(s): ' . "\n";
foreach($search as $q => $n) {
    echo '  - with ' . $q . ' difference(s), ' . count($n) . ' match(es) found:' . "\n";

    foreach($n as $i => $pos)
        echo '    - ' . substr($y, $pos['i'], -$pos['i']+$pos['j']) . ' ;' . "\n";
}

Auto-complétion

Proposition de mots clés