PHP MySQL per permutazioni su MySQL Tabella

Question

Ho una tabella mysql con 7 colonne, su cui ogni riga contiene valori interi.

Ho un sito semplice che riceve i valori dall'utente e devo provare a vedere se i valori inviati dall'utente corrispondono o sono simili a una qualsiasi delle righe della tabella.

Quindi l'utente scrive ad es. 1 2 3 4 5 6 7 come input.

Devo scoprire se una delle righe nella mia tabella è simile ad essa senza ordine. Quindi 1 2 3 4 5 6 7 = 7 6 5 4 3 2 1 e così via. La tabella my contiene più di 40.000 righe di dati.

Devo anche vedere se condividono almeno 5, 6 o 7 cifre in comune.

Ciò significa utilizzare le permutazioni per trovare tutte le combinazioni possibili. Tuttavia qual è l'approccio migliore per un simile problema?

1. Prendere l'input da parte dell'utente e ottenere tutte le permutazioni e partita contro la prima fila, seconda fila, ecc e riferire se trovato? In alternativa, fai il contrario, prendi una riga dalla tabella e ottieni tutte le permutazioni e fai la corrispondenza con l'input dell'utente?

2. Che dire della memoria e dell'uso della CPU quando si passa attraverso un tavolo così grande con così tante permutazioni?

Grazie per eventuali suggerimenti su questo! Souciance

Answer 1

un metodo leggero potrebbe essere quello di aggiungere un campo aggiuntivo nel database, che è una versione ordinata numericamente di tutti e 7 i campi combinati.

es. se i dati nel database erano 2 4 7 6 5 1 3, il campo della combinazione sarebbe 1234567

Quindi, durante il confronto, ordinare numericamente la risposta dell'utente e confrontarla con il campo della combinazione nel database.

A seconda di cosa si sta facendo, è possibile scrivere la query come questo

select * from table where combination like '12%' or combination like '123%' 

Se sai quello che il numero minimo di numeri corrispondenti deve essere, che sarebbe alleggerire la query

Per scoprire quanto sono simili a ciò che hanno scritto rispetto a ciò che è presente nel database. È possibile utilizzare la funzione PHP levenshtein: http://php.net/manual/en/function.levenshtein.php

$result = levenshtein($input,$combination); 

Answer 2

ho paura non è possibile costruire query problema come questo davvero efficiente.

Si può costruire WHERE clausola LIKE:

(`1` IN ARRAY(1,2,3,4,5,6,7) 
    AND `2` IN ARRAY(1,2,3,4,5,6,7) 
    AND `3` IN ARRAY(1,2,3,4,5,6,7) 
    AND `4` IN ARRAY(1,2,3,4,5,6,7) 
    AND `5` IN ARRAY(1,2,3,4,5,6,7)) 
OR 
(`1` IN ARRAY(1,2,3,4,5,6,7) 
    AND `2` IN ARRAY(1,2,3,4,5,6,7) 
    AND `3` IN ARRAY(1,2,3,4,5,6,7) 
    AND `4` IN ARRAY(1,2,3,4,5,6,7) 
    AND `6` IN ARRAY(1,2,3,4,5,6,7)) 
-- Each combination 

ma che sarebbe un inferno di una condizione.D'altra parte si può provare a utilizzare combinazione di:

• IN()
• IF()
• HAVING

Prima di controllo se colonna 1 contiene informazioni:

IF(`1` IN ARRAY(1,2,3,4,5,6,7), 1, 0) 

Poi sum tutti quei dati:

SELECT (
    IF(`1` IN ARRAY(1,2,3,4,5,6,7), 1, 0) + 
    IF(`2` IN ARRAY(1,2,3,4,5,6,7), 1, 0) + 
    IF(`3` IN ARRAY(1,2,3,4,5,6,7), 1, 0) + 
    IF(`4` IN ARRAY(1,2,3,4,5,6,7), 1, 0) + 
    IF(`5` IN ARRAY(1,2,3,4,5,6,7), 1, 0) + 
    IF(`6` IN ARRAY(1,2,3,4,5,6,7), 1, 0) + 
    IF(`7` IN ARRAY(1,2,3,4,5,6,7), 1, 0) 
) AS `matches_cnt` 
FROM t1 
HAVING `matches_cnt` >= 5 

Questo itererà attraverso tutte le righe e le condizioni sono piuttosto complesse (quindi le prestazioni del letto).

Si può anche provare a sostituire i valori da stringa binaria, per esempio:

1,2,7 = 01000011 

e quindi calcolare Hamming distance tra il record di controllati e di database, ma questo sarà solo diminuire la complessità della condizione, ma hanno bisogno di iterare attraverso tutti i record rimarrà lo stesso.

Attuazione in mysql con:

• XOR
• BIT_COUNT

sostituirà prima parte da:

SELECT (
    $MAX_NUMBER$ - BIT_COUNT(XOR(`binary_representation`, $DATA_FROM_USER$)) 
) AS `matches_cnt` 

Answer 3

In uno schema normalizzato completa questo è un singolo avente query

Supponiamo vostra tavola con pk come:

create table T1 
(pk char (1), a1 int, a2 int, a3 int, a4 int, a5 int, a6 int, a7 int); 

insert into T1 values 
('a',1,2,3,4,5,6,7), 
('b',2,3,4,5,6,7,8), 
('z',10,11,12,13,14,15,16); 

In questo momento, siamo in grado di normalizzare i dati come:

select 
    pk, 
    case a 
    when 1 then a1 
    when 2 then a2 
    when 3 then a3 
    when 4 then a4 
    when 5 then a5 
    when 6 then a6 
    when 7 then a7 
    end 
    as v 
from T1 
cross join 
    (select 1 as a from dual union all 
    select 2 as a from dual union all 
    select 3 as a from dual union all 
    select 4 as a from dual union all 
    select 5 as a from dual union all 
    select 6 as a from dual union all 
    select 7 as a from dual) T2 

Nella query precedente, è facile per soddisfare le vostre esigenze con un singolo avente:

select pk 
from 
(
select 
    pk, 
    case a 
    when 1 then a1 
    when 2 then a2 
    when 3 then a3 
    when 4 then a4 
    when 5 then a5 
    when 6 then a6 
    when 7 then a7 
    end 
    as v 
from T1 
cross join 
    (select 1 as a from dual union all 
    select 2 as a from dual union all 
    select 3 as a from dual union all 
    select 4 as a from dual union all 
    select 5 as a from dual union all 
    select 6 as a from dual union all 
    select 7 as a from dual) T2 
) T 
where 
    T.v in (4,5,6,7,8,9,10) 
group by pk 
having           <-- The Having 
    count(pk) > 4 

Results:

| PK | 
------ 
| b |