PermissiveResearch par Jérôme Morissard

PermissiveResearchpar Jérôme Morissard

@leverdeterreleverdeterre

Cocoheads / Paris - Meetup du 09/05/2015

PermissiveResearch

Contexte :

• Application de GED (application de gestion de documents),

• Recherche dans PDF,

• Recherche dans des objets CoreData,

• Recherche dans les plist.

Pourquoi ce composant ?

PermissiveResearch

Les problèmes :

• Recherche dans un objet, il faut une ou plusieurs propriétés.

• Recherche dans des objets hétérogènes, il faut prévoir des méthodes de recherche spécifiques par type d’objet.

• La recherche est exacte, mais ne pourrait - elle pas m’autoriser quelques fautes ?

• Taille du clavier, sur iPhone j’ai parfois l’impression d’avoir des gros doigts.

Pourquoi ce composant ?

PermissiveResearch

PermissiveResearchUn algorithme biologique

http://fr.wikipedia.org/wiki/Algorithme_de_Smith-Waterman

PermissiveResearchUn algorithme biologique

http://fr.wikipedia.org/wiki/Algorithme_de_Smith-Waterman

• Dans les années 80, la grande question était de classer les être vivants,

• Comment les classer ?

• En comparant leurs séquence d’ADN.

PermissiveResearchUn algorithme de Smith et Waterman (1981)

http://fr.wikipedia.org/wiki/Algorithme_de_Smith-Waterman

L'algorithme de Smith-Waterman est un algorithme optimal qui donne un alignement correspondant au meilleur score possible de correspondance entre les acides aminés ou les nucléotides des deux séquences.

Le calcul de ce score repose sur l'utilisation de matrices de similarité ou matrices de substitution.

PermissiveResearchUn algorithme de Smith et Waterman (1981)

Séquence 1 : FATCATY Séquence 2 : CATFAST

Séquence 1 : FATCATY Séquence 2 : CATFAST

Alignement 1Séquence 1 : FATCA-TY Séquence 2 : CATFAST

Alignement 2Séquence 1 : FATCATY——— Séquence 2 : ———CATFAST

Alignement 3

ThréonineSérine

TyrosinePhénylalanine

Pour trouver le meilleur alignement, il faut trouver le bien comprendre ce que l’on peut substituer.

PermissiveResearchSmith et Waterman : Matrice de similarité (nucléotide)

Alignement nucléotides

• alphabet : 4 lettres

PermissiveResearchSmith et Waterman : Matrice de similarité (acidé aminé)

Alignement acide aminés

• alphabet : 22 lettres

PermissiveResearchUn algorithm de Smith et Waterman (1981)

Séquence 1 : FATCATY Séquence 2 : CATFAST

F A T C A T YT 0 0 5 0 0 5 0CAGSFA

PermissiveResearchUn algorithm de Smith et Waterman (1981)

Séquence 1 : FATCATY Séquence 2 : CATFAST

F A T C A T YT 0 0 5 0 0 5 0C 0 0 0 14 8 2 3AGSFA

Pour chaque cellule, on maximise le score

PermissiveResearchUn algorithm de Smith et Waterman (1981)

Séquence 1 : FATCATY Séquence 2 : CATFAST

F A T C A T YT 0 0 5 0 0 5 0C 0 0 0 14 8 2 3A 0 4 0 8 18 12 6GSFA

Pour chaque cellule, on maximise le score

PermissiveResearchUn algorithm de Smith et Waterman (1981)

Séquence 1 : FATCATY Séquence 2 : CATFAST

F A T C A T YT 0 0 5 0 0 5 0C 0 0 0 14 8 2 3A 0 4 0 8 18 12 6GSFA

Pour chaque cellule, on maximise le score

PermissiveResearchUn algorithm de Smith et Waterman (1981)

Séquence 1 : FATCATY Séquence 2 : CATFAST

F A T C A T YT 0 0 5 0 0 5 0C 0 0 0 14 8 2 3A 0 4 0 8 18 12 6GSFA

Pour chaque cellule, on maximise le score

PermissiveResearchUn algorithm de Smith et Waterman (1981)

Séquence 1 : FATCATY Séquence 2 : CATFAST

F A T C A T YT 0 0 5 0 0 5 0C 0 0 0 14 8 2 3A 0 4 0 8 18 12 6GSFA

Pour chaque cellule, on maximise le score

PermissiveResearchUn algorithm de Smith et Waterman (1981)

Séquence 1 : FATCATY Séquence 2 : CATFAST

F A T C A T YT 0 0 5 0 0 5 0C 0 0 0 14 8 2 3A 0 4 0 8 18 12 6G 0 0 2 2 12 16 10SFA

PermissiveResearchUn algorithm de Smith et Waterman (1981)

Séquence 1 : FATCATY Séquence 2 : CATFAST

F A T C A T YT 0 0 5 0 0 5 0C 0 0 0 14 8 2 3A 0 4 0 8 18 12 6G 0 0 2 2 12 16 10S 0 0 5 1 6 17 14FA

PermissiveResearchUn algorithm de Smith et Waterman (1981)

Séquence 1 : FATCATY Séquence 2 : CATFAST

F A T C A T YT 0 0 5 0 0 5 0C 0 0 0 14 8 2 3A 0 4 0 8 18 12 6G 0 0 2 2 12 16 10S 0 0 5 1 6 17 14F 6 0 0 3 0 11 20A

PermissiveResearchUn algorithm de Smith et Waterman (1981)

Séquence 1 : FATCATY Séquence 2 : CATFAST

F A T C A T YT 0 0 5 0 0 5 0C 0 0 0 14 8 2 3A 0 4 0 8 18 12 6G 0 0 2 2 12 16 10S 0 0 5 1 6 17 14F 6 0 0 3 0 11 20A 0 10 4 0 7 5 14

PermissiveResearchUn algorithm de Smith et Waterman (1981)

Séquence 1 : FATCATY Séquence 2 : CATFAST

F A T C A T YT 0 0 5 0 0 5 0C 0 0 0 14 8 2 3A 0 4 0 8 18 12 6G 0 0 2 2 12 16 10S 0 0 5 1 6 17 14F 6 0 0 3 0 11 20A 0 10 4 0 7 5 14

PermissiveResearchPerformance (iPhone 4)

Données NSPredicate Permissive Research

5272 villes 250ms 1s

52720 villes 2,5s 8s

PermissiveResearch Vs NSPredicate : l’algorithme de PermissiveResearch à une plus grande complexité algorithmique.

PermissiveResearchPerformance (iPhone 4)

Données NSPredicate Permissive Research

5272 villes 250ms 1s

52720 villes 2,5s 8s

Les 2 algorithmes ont une complexité temps ~linéaire : f(nombre de données)

PermissiveResearchOptimisation : Commençons par une heuristique

Une heuristique est une méthode de calcul qui fournit rapidement une solution réalisable, pas nécessairement optimale ou exacte, pour un problème d'optimisation difficile.

http://fr.wikipedia.org/wiki/Heuristique_(mathématiques)

PermissiveResearchOptimisation : Heuristique

Données Segments

Découpage de nos données en segments, c’est un paramètre configurable (ici, une longueur de 3)

PermissiveResearchOptimisation : Heuristique

Segments Données

Pour un segment, on sait retrouver les données associées

PermissiveResearchOptimisation : Heuristique

autre stationMa cherche

aut

utr

tre

sta

tat

tion

On recherche les objets avec un maximum d’étiquettes

PermissiveResearchOptimisation : Heuristique

SCNFMa cherche

SCN

CNF

On garde les X meilleurs

xxxxxxx

PermissiveResearchOptimisation : Heuristique

Données NSPredicate Permissive Research (heuristique)

5272 villes 250ms 30ms

52720 villes 2,5s 0,6s

C’est rapide … mais : c’est moins précis, la complexité espace augmente (les segments) et on ne tolère d’erreur.

PermissiveResearch

Les problèmes :

• Recherche dans un objet, il faut une ou plusieurs propriétés,

• Recherche dans des objets hétérogènes, il faut prévoir des méthodes de recherche spécifiques par type d’objet,

• La recherche est exacte, mais ne pourrait - elle pas m’autoriser quelques fautes ?

• Taille du clavier, sur iPhone j’ai parfois l’impression d’avoir des gros doigts.

Pourquoi ce composant ?

PermissiveResearchOptimisation : Heurexacte (Heuristique + Exacte)

DonnéesHeuristique rapide, on supprime 90% des données. On garde les objets qui ont un maximum fragments communs.

Sous-ensemble de données

On analyse finement les objets restants

Sous-sous-ensemble de données

Retour des résultats

PermissiveResearchOptimisation : Heuristique

Données NSPredicatePermissive Research

(heuristique)

Permissive Research

(heurexact)

5272 villes 250ms 30ms 300ms

52720 villes 2,5s 0,6s 2,4s

On conserve la performance, on a une bonne approximation, et on autorise des erreurs :)

PermissiveResearchLes améliorations à faire : matrice custom

Il faudrait faire une matrice sur pour gérer nos pondérer nos erreurs.

PermissiveResearch

Des questions ?