string - programacion - Cómo encontrar patrones similares en listas/matrices de cadenas

que es un array en java

Question

Estoy buscando formas de encontrar patrones coincidentes en listas o matrices de cadenas, específicamente en .NET, pero los algoritmos o la lógica de otros idiomas serían útiles.

Digamos que tengo 3 arrays (o en este caso específico List (Of String))

Array1
"Do"
"Re"
"Mi"
"Fa"
"So"
"La"
"Ti"

Array2
"Mi"
"Fa"
"Jim"
"Bob"
"So"

Array3
"Jim"
"Bob"
"So"
"La"
"Ti"

Quiero informar sobre las ocurrencias de los partidos de

("Mi", "Fa") In Arrays (1,2)
("So") In Arrays (1,2,3)
("Jim", "Bob", "So") in Arrays (2,3)
("So", "La", "Ti") in Arrays (1, 3)

... y cualquier otro.

Estoy usando esto para solucionar un problema, no para hacer un producto comercial de él específicamente, y preferiría no hacerlo a mano (hay 110 listas de alrededor de 100-200 elementos).

¿Hay algún algoritmo, código existente o ideas que me ayuden a lograr encontrar los resultados descritos?

Answer 1

Como otros han mencionado, la función que desea es Intersecar. Si usa .NET 3.0, considere usar la función Intersecar de LINQ.

Ver la siguiente publicación para más información

Considera usar LinqPAD para experimentar.

www.linqpad.net

Answer 2

Corté el programa a continuación en unos 10 minutos de Perl. No es perfecto, usa una variable global e imprime los recuentos de cada elemento visto por el programa en cada lista, pero es una buena aproximación a lo que desea hacer que es súper fácil de codificar.

¿De verdad quieres todas las combinaciones de todos los subconjuntos de los elementos comunes a cada matriz? Podría enumerar todos los elementos de una forma más inteligente si quisiera, pero si solo quisiera todos los elementos que existen al menos una vez en cada conjunto, podría usar el comando de Unix "grep -v 0" en el resultado a continuación y que mostraría usted la intersección de todos los elementos comunes a todas las matrices. Su pregunta le falta un poco de detalle, por lo que no puedo implementar perfectamente algo que resuelva su problema.

Si realiza más análisis de datos que programación, los scripts pueden ser muy útiles para hacer preguntas a partir de datos textuales como este. Si no sabes cómo codificar en un lenguaje de scripting como este, me gustaría pasar un mes o dos leyendo sobre cómo codificar en Perl, Python o Ruby. Pueden ser maravillosos para hacks únicos como este, especialmente en los casos en que realmente no sabes lo que quieres. El costo de tiempo y cerebro de escribir un programa como este es muy bajo, de modo que (si eres rápido) puedes escribirlo y volver a escribirlo varias veces mientras exploras la definición de tu pregunta.

#!/usr/bin/perl -w

use strict;

my @Array1 = ( "Do", "Re", "Mi", "Fa", "So", "La", "Ti");
my @Array2 = ( "Mi", "Fa", "Jim", "Bob", "So" );
my @Array3 = ( "Jim", "Bob", "So", "La", "Ti" );

my %counts;
sub count_array {
    my $array = shift;
    my $name  = shift;
    foreach my $e (@$array) {
        $counts{$e}{$name}++;
    }
}

count_array( /@Array1, "Array1" );
count_array( /@Array2, "Array2" );
count_array( /@Array3, "Array3" );

my @names = qw/ Array1 Array2 Array3 /;
print join '' '', (''element'',@names);
print "/n";

my @unique_names = keys %counts;
foreach my $unique_name (@unique_names) {
    my @counts = map {
        if ( exists $counts{$unique_name}{$_} ) {
            $counts{$unique_name}{$_};
        } else {
            0;
        }
    }
    @names;

    print join '' '', ($unique_name,@counts);
    print "/n";
}

La salida del programa es:

element Array1 Array2 Array3
Ti 1 0 1
La 1 0 1
So 1 1 1
Mi 1 1 0
Fa 1 1 0
Do 1 0 0
Bob 0 1 1
Jim 0 1 1
Re 1 0 0

Answer 3

Estoy seguro de que hay una manera MUCHO más elegante, pero ...

Como esto no es código de producción, ¿por qué no simplemente piratearlo y convertir cada matriz en una cadena delimitada, luego buscar cada cadena para el patrón que desea? es decir

        private void button1_Click(object sender, EventArgs e)
        {

            string[] array1 = { "do", "re", "mi", "fa", "so" };
            string[] array2 = { "mi", "fa", "jim", "bob", "so" };
            string[] pattern1 = { "mi", "fa" };
            MessageBox.Show(FindPatternInArray(array1, pattern1).ToString());
            MessageBox.Show(FindPatternInArray(array2, pattern1).ToString());

        }

        private bool FindPatternInArray(string[] AArray, string[] APattern)
        {
            return string.Join("~", AArray).IndexOf(string.Join("~", APattern)) >= 0;
        }

Answer 4

La forma más simple de codificar sería construir un diccionario y luego recorrer cada elemento de cada matriz. Para cada elemento haz esto:

Verifique si el artículo está en el dictonario, de ser así, agregue la lista a la matriz. Si el artículo no está en el diccionario, agrégalo y la lista.

Como dijiste que esto no es el rendimiento del código de producción, no importa, por lo que este enfoque debería funcionar bien.

Answer 5

Parece que quiere usar una función de intersección en conjuntos de datos. La intersección selecciona elementos que son comunes en ambos (o más) conjuntos.

El problema con este punto de vista es que los conjuntos no pueden contener más de uno de cada elemento, es decir, no más de un Jim por conjunto, tampoco puede reconocer varios elementos en una fila contando como un patrón; sin embargo, puede modificar una función de comparación para ver más para ver solo eso.

Hay funciones como intersect que funcionan en bolsas (que son como sets, pero toleran elementos idénticos).

Estas funciones deberían ser estándar en la mayoría de los idiomas o bastante fáciles de escribir.

Answer 6

Primero, comienza contando cada artículo. Usted hace una lista temporal: "Do" = 1, "Mi" = 2, "So" = 3, etc. Puede eliminar de la lista temporal todos los que coinciden = 1 (por ejemplo, "Do"). La lista temporal contiene la lista de elementos no únicos (guárdelo en algún lugar).

Ahora, intenta hacer listas de dos de uno en la lista temporal y un seguimiento en las listas originales. "Entonces" + "La" = 2, "Bob" + "So" = 2, etc. Quite los que tienen = 1. Usted tiene las listas de parejas que aparecen al menos dos veces (guárdelas en algún lugar).

Ahora, intente hacer listas de 3 elementos, tomando un par de la lista temporal, y tome lo siguiente de las listas originales. ("Mi", "Fa") + "So" = 1, ("Mi", "Fa") + "Jim" = 1, ("Así que", "La") + "Ti" = 2 Quita los que con = 1. Tiene las listas de 3 elementos que aparecen al menos dos veces (guárdelo).

Y continúa así hasta que la lista temporal esté vacía.

Al final, tomas todas las listas guardadas y las fusionas.

Este algoritmo no es óptimo (creo que podemos mejorar con estructuras de datos adecuadas), pero es fácil de implementar :)

Answer 7

Supongamos que una contraseña consistía en una cadena de nueve caracteres del alfabeto inglés (26 caracteres). Si cada contraseña posible pudiera probarse en un milisegundo, ¿cuánto tiempo tomaría probar todas las contraseñas posibles?

Answer 8

Aquí hay una solución que usa el módulo SuffixTree para localizar subsequences:

#!/usr/bin/env python
from SuffixTree  import SubstringDict
from collections import defaultdict
from itertools   import groupby
from operator    import itemgetter
import sys

def main(stdout=sys.stdout):
    """
    >>> import StringIO
    >>> s = StringIO.StringIO()
    >>> main(stdout=s)
    >>> print s.getvalue()
    [[''Mi'', ''Fa'']] In Arrays (1, 2)
    [[''So'', ''La'', ''Ti'']] In Arrays (1, 3)
    [[''Jim'', ''Bob'', ''So'']] In Arrays (2, 3)
    [[''So'']] In Arrays (1, 2, 3)
    <BLANKLINE>
    """
    # array of arrays of strings
    arr = [
        ["Do", "Re", "Mi", "Fa", "So", "La", "Ti",],
        ["Mi", "Fa", "Jim", "Bob", "So",],
        ["Jim", "Bob", "So", "La", "Ti",],
    ]

####    # 28 seconds  (27 seconds without lesser substrs inspection (see below))
####    N, M = 100, 100
####    import random
####    arr = [[random.randrange(100) for _ in range(M)] for _ in range(N)]

    # convert to ASCII alphabet (for SubstringDict)
    letter2item = {}
    item2letter = {}
    c = 1
    for item in (i for a in arr for i in a):
        if item not in item2letter:
            c += 1
            if c == 128:
                raise ValueError("too many unique items; "
                                 "use a less restrictive alphabet for SuffixTree")
            letter = chr(c)
            letter2item[letter] = item
            item2letter[item] = letter
    arr_ascii = [''''.join(item2letter[item] for item in a) for a in arr]

    # populate substring dict (based on SuffixTree)
    substring_dict = SubstringDict()
    for i, s in enumerate(arr_ascii):
        substring_dict[s] = i+1

    # enumerate all substrings, save those that occur more than once
    substr2indices = {}
    indices2substr = defaultdict(list)
    for str_ in arr_ascii:
        for start in range(len(str_)):
            for size in reversed(range(1, len(str_) - start + 1)):
                substr = str_[start:start + size]
                if substr not in substr2indices:
                    indices = substring_dict[substr] # O(n) SuffixTree
                    if len(indices) > 1:
                        substr2indices[substr] = indices
                        indices2substr[tuple(indices)].append(substr)
####                        # inspect all lesser substrs
####                        # it could diminish size of indices2substr[ind] list
####                        # but it has no effect for input 100x100x100 (see above)
####                        for i in reversed(range(len(substr))):
####                            s = substr[:i]
####                            if s in substr2indices: continue
####                            ind = substring_dict[s]
####                            if len(ind) > len(indices):
####                                substr2indices[s] = ind
####                                indices2substr[tuple(ind)].append(s)
####                                indices = ind
####                            else:
####                                assert set(ind) == set(indices), (ind, indices)
####                                substr2indices[s] = None
####                        break # all sizes inspected, move to next `start`

    for indices, substrs in indices2substr.iteritems():
        # remove substrs that are substrs of other substrs
        substrs = sorted(substrs, key=len) # sort by size
        substrs = [p for i, p in enumerate(substrs)
                   if not any(p in q  for q in substrs[i+1:])]
        # convert letters to items and print
        items = [map(letter2item.get, substr) for substr in substrs]
        print >>stdout, "%s In Arrays %s" % (items, indices)

if __name__=="__main__":
    # test
    import doctest; doctest.testmod()
    # measure performance
    import timeit
    t = timeit.Timer(stmt=''main(stdout=s)'',
                     setup=''from __main__ import main; from cStringIO import StringIO as S; s = S()'')
    N = 1000
    milliseconds = min(t.repeat(repeat=3, number=N))
    print("%.3g milliseconds" % (1e3*milliseconds/N))

Tarda unos 30 segundos en procesar 100 listas de 100 elementos cada una. SubstringDict en el código anterior puede ser emulado por grep -F -f .

Vieja solución:

En Python (guárdelo en el archivo ''group_patterns.py''):

#!/usr/bin/env python
from collections import defaultdict
from itertools   import groupby

def issubseq(p, q):
    """Return whether `p` is a subsequence of `q`."""
    return any(p == q[i:i + len(p)] for i in range(len(q) - len(p) + 1))

arr = (("Do", "Re", "Mi", "Fa", "So", "La", "Ti",),
       ("Mi", "Fa", "Jim", "Bob", "So",),
       ("Jim", "Bob", "So", "La", "Ti",))

# store all patterns that occure at least twice
d = defaultdict(list) # a map: pattern -> indexes of arrays it''s within
for i, a in enumerate(arr[:-1]):
    for j, q in enumerate(arr[i+1:]): 
        for k in range(len(a)):
            for size in range(1, len(a)+1-k):
                p = a[k:k + size] # a pattern
                if issubseq(p, q): # `p` occures at least twice
                    d[p] += [i+1, i+2+j]

# group patterns by arrays they are within
inarrays = lambda pair: sorted(set(pair[1]))
for key, group in groupby(sorted(d.iteritems(), key=inarrays), key=inarrays):
    patterns = sorted((pair[0] for pair in group), key=len) # sort by size
    # remove patterns that are subsequences of other patterns
    patterns = [p for i, p in enumerate(patterns)
                if not any(issubseq(p, q)  for q in patterns[i+1:])]
    print "%s In Arrays %s" % (patterns, key)

El siguiente comando:

$ python group_patterns.py

huellas dactilares:

[(''Mi'', ''Fa'')] In Arrays [1, 2]
[(''So'',)] In Arrays [1, 2, 3]
[(''So'', ''La'', ''Ti'')] In Arrays [1, 3]
[(''Jim'', ''Bob'', ''So'')] In Arrays [2, 3]

La solución es terriblemente ineficiente.