PUBLIC MARKS from parmentierf with tag algorithme

Latent Semantic Analysis (LSA) is a mathematical method that tries to bring out latent relationships within a collection of documents.

This web-site is the hub of the online game AI community. It includes a leading blog about artificial intelligence in games, a friendly and buzzing forum, as well as a knowledge base in the wiki.

The default sort functions in almost every programming language are poorly suited for human consumption. What do I mean by that?

Le Double Metaphone est un algorithme de recherche phonétique écrit par Lawrence Philips et est la deuxième génération de l'algorithme Metaphone. Son implémentation a été décrite en juin 2000 dans le magazine C/C Users Journal. Il est appelé « Double » car il peut retourner un code primaire et secondaire pour une chaîne de caractères (String) ; cela compte pour des cas ambigus ou pour des variantes multiples avec des ascendances communes. Par exemple, l'encodage du nom « Smith » rapporte le code primaire SM0 et le code secondaire XMT, lorsque le nom « Schmidt » rapporte le code primaire XMT et le code secondaire de SMT ; les deux ont XMT en commun.

SplitsTree4 is the leading application for computing evolutionary networks from molecular sequence data. Given an alignment of sequences, a distance matrix or a set of trees, the program will compute a phylogenetic tree or network using methods such as split decomposition, neighbor-net, consensus network, super networks methods or methods for computing hybridization or simple recombination networks. SplitsTree4 is an all-new implementation of the SplitsTree3 software written in Java.

Thèse de doctorat de Sylvie Hamel - recherche approximative de chaînes de caractères.

This is a dictionary of algorithms, algorithmic techniques, data structures, archetypical problems, and related definitions. Algorithms include common functions, such as Ackermann's function. Problems include traveling salesman and Byzantine generals. Some entries have links to implementations and more information. Index pages list entries by area and by type. The two-level index has a total download 1/20 as big as this page.

Approximate matching

I described the algorithms in two classes: equivalence methods and similarity ranking methods. Equivalence methods return a Boolean result, whereas the similarity ranking methods return a numeric similarity measure or distance metric. In information retrieval systems, it is possible to mix methods to produce a faster hybrid approach. A typical approach is to employ a two-pass mechanism in which an equivalence method is used by the database as a first pass filter, and a ranked similarity method is applied to the filtered entries for the second pass. Ranked similarity methods tend to be algorithmically more complex than equivalence methods, so are usually implemented as custom code outside of the database.

We survey the current techniques to cope with the problem of string matching allowing errors. This is becoming a more and more relevant issue for many fast growing areas such as information retrieval and computational biology. We focus on online searching and mostly on edit distance, explaining the problem and its relevance, its statistical behavior, its history and current developments, and the central ideas of the algorithms and their complexities.

Une bonne présentation sur la recherche approximative de chaînes (références, algos, ...)

Our algorithm has the peculiar property that, roughly speaking, the longer the pattern is, the faster the algorithm goes. Furthermore, the algorithm is ``sublinear'' in the sense that it generally looks at fewer characters than it passes. The algorithm is described in

The problem: given a (short) pattern and a (long) text, both strings, determine whether the pattern appears somewhere in the text. Last time we saw how to do this with finite automata. This time we'll go through the Knuth-Morris-Pratt (KMP) algorithm, which can be thought of as an efficient way to build these automata. I also have some working C source code which might help you understand the algorithm better.

Vous ne connaissez pas les microformats ? Bon. Ca va être un peu technique a expliquer. Pour Frédéric Cavazza, consultant, le principal intérêt est de “rendre exploitable par des robots du contenu à la base crée pour des humains. Exploitable veut dire qu’à partir d’une requête structurée il est possible de rapatrier des informations précises. Par exemple « va sur le site XX pour parcourir sa liste de liens et me rapatrier tous les sites dont les auteurs se connaissent personnellement ». Ça n’a l’air de rien, mais ce type de requête structurée peut vous éviter d’avoir à investir des milliards de dollars dans un algorithme d’indexation plus performant que celui de Google.”

Comment dans une liste de nom de personne arriver à retrouver un certain DUPONT ou DUPOND ou DUPAN ou encore DEPAIN ??? C’est simple, il suffit de se baser sur la consonance et non sur les mots eux-mêmes. Tous les algorithmes de Soundex reposent sur un principe de base qui consiste à codifier le mot en éliminant les lettres en doubles, les lettres muettes (H en particulier) et en rapprochant les sons de certaines lettres. Une fois cette codification obtenue on la stocke auprès de la donnée de base et on effectue la recherche par comparaison directe entre le Soundex ainsi obtenu et le mot recherché codifié lui aussi en Soundex. La recherche en est donc très performante puisqu’elle aboutit à une requête dont le critère est l’égalité, et pour peu que l’on place un index sur le champ qui stocke le code du soundex, alors elle s’avère aussi rapide que de trouver un enregistrement pas sa clef.