Fonction de partage de N-gramme pour comparaison de similarité de chaîne

Question

Dans le cadre de l'exercice pour mieux comprendre F # que j'apprends actuellement, j'ai écrit la fonction à diviser la chaîne donnée en n-grammes.
1) J'aimerais recevoir des commentaires sur ma fonction: cela peut-il être écrit plus simplement ou de manière plus efficace?

2) Mon objectif général est d'écrire une fonction qui retourne une similarité de chaîne (sur une échelle de 0.0 .. 1.0) basée sur la similarité de n-gram; Cette approche fonctionne-t-elle bien pour les comparaisons de chaînes courtes, ou cette méthode peut-elle être utilisée de manière fiable pour comparer de grandes chaînes (comme des articles par exemple).

3) Je suis conscient du fait que les comparaisons de n-grammes ignorent le contexte de deux chaînes. Quelle méthode suggéreriez-vous pour atteindre mon but?

//s:string - target string to split into n-grams 
//n:int - n-gram size to split string into 
let ngram_split (s:string, n:int) = 
    let ngram_count = s.Length - (s.Length % n) 
    let ngram_list = List.init ngram_count (fun i -> 
     if(i + n >= s.Length) then 
     s.Substring(i,s.Length - i) + String.init ((i + n) - s.Length) 
      (fun i -> "#") 
     else 
      s.Substring(i,n) 
    ) 
    let ngram_array_unique = ngram_list 
          |> Seq.ofList 
          |> Seq.distinct 
          |> Array.ofSeq 

//produce tuples of ngrams (ngram string,how much occurrences in original string) 

    Seq.init ngram_array_unique.Length (fun i -> (ngram_array_unique.[i], 
     ngram_list |> List.filter(fun item -> item = ngram_array_unique.[i]) 
            |> List.length) 
             ) 

Answer 1

Votre code semble OK pour moi. Depuis l'extraction de ngram et comparaison de similarité sont très souvent utilisés. Vous devriez considérer quelques problèmes d'efficacité ici.

Le motif de MapReduce est très approprié pour votre problème de comptage de fréquence:

1. obtenir une chaîne, émettront (mot, 1) paires sur

2. font un regroupement des mots et ajoute tout le comptage ensemble .

   let wordCntReducer (wseq: seq<int*int>) =

   wseq 
       |> Seq.groupBy (fun (id,cnt) -> id) 
       |> Seq.map (fun (id, idseq) -> 
         (id, idseq |> Seq.sumBy(fun (id,cnt) -> cnt))) 
   (* test: wordCntReducer [1,1; 2,1; 1,1; 2,1; 2,2;] *) 
   

Vous devez également maintenir une carte <word,int> pendant votre immeuble ngram pour un ensemble de chaînes. Comme il est beaucoup plus efficace de gérer les entiers plutôt que les chaînes lors du traitement ultérieur.

(2) pour comparer la distance entre deux chaînes courtes. Une pratique courante consiste à utiliser Edit Distance en utilisant une programmation dynamique simple. Pour calculer la similarité entre les articles, une méthode de pointe consiste à utiliser la représentation des entités TFIDF.En fait, le code ci-dessus est pour le comptage des fréquences, extrait de ma bibliothèque de data mining.

(3) Il existe des méthodes NLP complexes, par ex. les noyaux d'arbre basés sur l'arbre d'analyse, pour coopérer avec les informations de contexte.

Answer 2

Je ne sais pas beaucoup sur l'évaluation de la similarité des chaînes, donc je ne peux pas vous donner beaucoup de commentaires concernant les points 2 et 3. Cependant, voici quelques suggestions qui peuvent aider à rendre votre application plus simple .

La plupart des opérations que vous devez effectuer sont déjà disponibles dans certaines fonctions de bibliothèque F # pour travailler avec des séquences (listes, tableaux, etc.). Les chaînes sont également des séquences (de caractères), vous pouvez donc écrire:

open System 

let ngramSplit n (s:string) = 
    let ngrams = Seq.windowed n s 
    let grouped = Seq.groupBy id ngrams 
    Seq.map (fun (ngram, occurrences) -> 
    String(ngram), Seq.length occurrences) grouped 

La fonction Seq.windowed implémente une fenêtre glissante, ce qui est exactement ce dont vous avez besoin pour extraire les n-grammes de votre chaîne. La fonction Seq.groupBy recueille les éléments d'une séquence (n-grammes) dans une séquence de groupes contenant des valeurs avec la même clé. Nous utilisons id pour calculer la clé, ce qui signifie que le n-gramme est lui-même la clé (et donc nous obtenons des groupes, où chaque groupe contient les mêmes n-grammes). Ensuite, nous convertissons simplement n-gram en chaîne et comptons le nombre d'éléments dans le groupe.

Vous pouvez écrire la fonction entière comme un seul pipeline de traitement comme celui-ci:

let ngramSplit n (s:string) = 
    s |> Seq.windowed n 
    |> Seq.groupBy id 
    |> Seq.map (fun (ngram, occurrences) -> 
     String(ngram), Seq.length occurrences) 

Answer 3

Je pense que vous avez de bonnes réponses à la question (1).

Question (2):

Vous voulez probablement similarité cosinus de comparer deux collections arbitraires de n-grammes (plus mieux). Cela vous donne une plage de 0,0 à 1,0 sans aucune mise à l'échelle nécessaire. Le Wikipedia page gives an equation et la traduction F # est assez simple:

let cos a b = 
    let dot = Seq.sum (Seq.map2 (*) a b) 
    let magnitude v = Math.Sqrt (Seq.sum (Seq.map2 (*) v v)) 
    dot/(magnitude a * magnitude b) 

Pour l'entrée, vous devez exécuter quelque chose comme la réponse de Tomas pour obtenir deux cartes, puis supprimer les clés qui existent dans une seule:

let values map = map |> Map.toSeq |> Seq.map snd 
let desparse map1 map2 = Map.filter (fun k _ -> Map.containsKey k map2) map1 
let distance textA textB = 
    let a = ngramSplit 3 textA |> Map.ofSeq 
    let b = ngramSplit 3 textB |> Map.ofSeq 
    let aValues = desparse a b |> values 
    let bValues = desparse b a |> values 
    cos aValues bValues 

Avec les n-grammes basés sur les personnages, je ne sais pas si vos résultats seront bons. Cela dépend du type de caractéristiques du texte qui vous intéresse. Je fais du traitement en langage naturel, donc habituellement, ma première étape est l'étiquetage de la partie du discours. Ensuite, je compare plus de n-grammes des parties du discours. J'utilise T'n'T pour cela, mais il a des problèmes de licence bizarro. Certains de mes collègues utilisent à la place ACOPOST, une alternative gratuite (comme dans la bière et la liberté). Je ne sais pas si la précision est bonne, mais l'étiquetage POS est un problème bien compris de nos jours, du moins pour l'anglais et les langues apparentées.

Question (3):

La meilleure façon de comparer deux chaînes qui sont presque identiques est Levenshtein distance. Je ne sais pas si c'est votre cas ici, bien que vous puissiez assouplir les hypothèses de plusieurs façons, par exemple pour comparer les chaînes d'ADN.

Le livre standard sur ce sujet est "Time Warps, String Edits, and Maromolecules" de Sankoff et Kruskal. C'est assez vieux (1983), mais donne de bons exemples d'adaptation de l'algorithme de base à un certain nombre d'applications.

Answer 4

Question 3:

Mon livre de référence est Computing Patterns in Strings par Bill Smyth