Classificare array di stringhe basata su punti in comune

Question

Ho lista enorme (200000) di stringhe (multi parola). Voglio gruppo queste stringhe basate su serie comman della partita parola tra queste stringhe. Non posso pensare di un algoritmo di tempo di calcolo bassa per questo

" AB 500 "
  "Bus AB 500 "
  " Notizie CA "
  " Notizie CA BLAH"

Il mio piano era
un. li tokenize a parole.
b. Creare un array globale gettoni
c. Confronto quelle stringhe con i token comuni.

Come avete indovinato questo non aiuta. Potete suggerire un algoritmo per questo? Sto scrivendo questo in Python ..

Answer 1

200000 non è più di tanto, si può fare questo

1. Split ogni stringa di ottenere gettoni per esempio. "News CA BLAH" -> [ "Blah", "CA", "News"]
2. creare una voce dict ogni lunghezza della lista per esempio in caso di [ "Blah", "CA", "News"] tutte le combinazioni in ordine
3. Ora basta ad anello attraverso il dict e vedere i gruppi

esempio di codice:

data="""AB 500
Bus AB 500
News CA
News CA BLAH"""

def getCombinations(tokens):
    count = len(tokens)
    for L in range(1,count+1):
        for i in range(count-L+1):
            yield tuple(tokens[i:i+L])

groupDict = {}
for s in data.split("\n"):
    tokens = s.split()
    for groupKey in getCombinations(tokens):
        if groupKey not in groupDict:
            groupDict[groupKey] = [s]
        else:
            groupDict[groupKey].append(s)

for group, values in groupDict.iteritems():
    if len(values) > 1:
        print group, "->", values

emette:

('News', 'CA') -> ['News CA', 'News CA BLAH']
('AB',) -> ['AB 500', 'Bus AB 500']
('500',) -> ['AB 500', 'Bus AB 500']
('CA',) -> ['News CA', 'News CA BLAH']
('AB', '500') -> ['AB 500', 'Bus AB 500']
('News',) -> ['News CA', 'News CA BLAH']

Answer 2

Vuoi dire qualcosa di simile?

>>> from collections import defaultdict
>>> L=["AB 500",
... "Bus AB 500",
... "News CA",
... "News CA BLAH"]
>>> d=defaultdict(list)
>>> for s in L:
...     for w in s.split():
...         d[w].append(s)
... 
>>> print d["News"]
['News CA', 'News CA BLAH']
>>> print d["CA"]
['News CA', 'News CA BLAH']
>>> print d["500"]
['AB 500', 'Bus AB 500']

Answer 3

A meno che la ripetizione di parole è una caratteristica importante per il vostro caso d'uso, suggerisco set. Cioè:.

thestrings = [
"AB 500",
"Bus AB 500",
"News CA",
"News CA BLAH",
]

thesets = dict((s, set(s.split())) for s in thestrings)

similarities = dict()
for s in thestrings:
  for o in thestrings:
    if s>=o: continue
    sims = len(thesets[s] & thesets[o])
    if not sims: continue
    similarities[s, o] = sims

for s, o in sorted(similarities, similarities.get, reverse=True):
  print "%-16r %-16r %2d" % (s, o, similarities[s, o])

E 'questo vicino a quello che stai cercando? Lo fa classificare le 4 corde si dà nel modo che desideri, ma questo è un campione molto debole, naturalmente, quindi sono di duplice controllo; -).

Answer 4

Che cosa accadrebbe, se la stringa "AB 500 Notizie CA" viene aggiunto alla tua lista? Fare i due gruppi di stringhe devono fondersi? Se no, come dividere la lista di stringhe e perché?

Un flusso di lavoro molto generale per problemi come questo (se ho capito bene) va in questo modo:

1. Ottenere una lista di coppie candidati tramite un invertiti Indice / Tutte le coppie di ricerca per analogia / < a href = "http://infolab.stanford.edu/~manku/papers/07www-duplicates.ppt" rel = "nofollow noreferrer"> Simhashing
2. Calc alcune funzioni di distanza per ciascuna coppia e riunire in un unico peso
3. Ogni coppia pesata ((a, b), peso) rappresenta ora un vantaggio in un grafico, che si possono raggruppare in "gruppi word-match" via gerarchica iterazione raggruppamento / potenza