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. Introduction: praeludo
    1. Presentation
    2. Background
    3. Audience
    4. Scope
  2. mark element: prestissimo
    1. Needs and usages
    2. Gecko implementation status
  3. 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
  4. User experience
    1. Matching search
      1. Pattern matching algorithms
      2. Phonetic algorithms
    2. Relevant search
      1. Weight and distance
      2. Group and section
  5. User interface


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).

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 user experience, i.e. finder experience, not the presentation, but only the way of how to find words in the document.

A first trivial approach is to search by purely textual matching, i.e. we search all matches that are likely to approach the searched sequence, either by pattern matching, with or without difference, or by phonetic. It does not combine the words and give them a weight, it is purely textual and aural. It does not concern the meaning of words, their semantics.

Pattern matching algorithms

There are differents ways, theories and algorithms to match a pattern on a document. We make a non-exaustive list.

Trivial search
Regular expression
Approximate search

Phonetic algorithms

A second approach, more experimental this time, is to search by relevance, i.e. taking into account the meaning of words. Either we can assigned a weight from a distance (textual, aural, spatial) or can grouped them (example given by using headings or semantic).

Weight and distance

Group and section


Text algorithms

Regular expression

The search input should understand the regular expression.

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 \bsimpl.\b will match:

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

We wonder if the PCRE engine would be used. It is based on a Nondeterministic Finite Automation, like Perl, Python, Java, .NET etc. used. But, a Deterministic Finite Automation would be faster, even if it is powerless, like MySQL, awk, egrep etc. used.

PCRE is a priori used by Webkit.

We also should take a look to the vector-binary model.

Approximate pattern matching

An other way to find better is to detect if the user would not have made typos. We can make an approximate pattern matching with differences.

Take this example — woefully simplistic —:

Try to match GATAA in CAGATAAGAGAA with at most one difference:

Levenshtein distance

The Levenshtein distance is a metric for measuring the amount of difference between two sequences. The Levenshtein distance between two strings is given by the minimum of operations needed to transform one string into the other, where an operation is an insertion, deletion or substitution of a single character.

For example, the Levenshtein distance between kitten and sitting is 3:

Since the following three edits change one into the other, and there is no way to do it with fewer than three edits:

In fine, if the distance between two words is lesser than n, we could recognized this word as matching.

If Levenshtein distance is not much as relevant as we hoped, we can take a look to the Hamming distance.

Words weight

Each word has a weight, that could be determined with the Hamming weight algorithm. It would be great to match all words that have a similar weight that the original word or sequence.

Euclidean distance

Phonetic algorithms

A phonetic algorithm is an algorithm for indexing of words by their pronunciation. Most phonetic algorithms were developed for use with the English language; consequently, applying the rules to words in other languages might not give a meaningful result.

Among the best-known phonetic algorithms are:

It should be hard to develop new algorithms for all Firefox supported languages (about 70 languages). A solution may exists with phonemes. It needs relfexions.

Smartcase

User interface

Matches arity

List of excerpts

List of relevant sections

Bubbled scrollbar

Smooth transition when jumping

Focus the current matched element

Page preview

Highlight viewable matches in a list

Darken the document except matches