[PHP / MySQL] Het onderling vergelijken van strings

[Donderpoes]

Goedenavond,

Ik heb een vraagstuk betreffende het vergelijken van strings met elkaar en de uitkomst van de vergelijking op te slaan in de database.

Uit een bestand haal ik een lijst van strings op. Dit zijn tags die zowel door gebruikers als geautomatiseerd aangemaakt zijn. Dit zijn er momenteel 20.399. Helaas staan er een behoorlijk aantal tags tussen welke eigenlijk één en dezelfde zijn of in iedergeval erg nauw verwant aan elkaar.

Bijvoorbeeld:

1. bad accessoires en badaccessoires
2. brandblusser en brandblussers en poeder brandblusser

Zoals je ziet zijn de tags in situatie één gelijk, uitgezonderd de spatie.
In situatie twee zijn er twee tags gelijk, afgezien van het feit dat er een verschil is tussen enkel- en meervoud. En dan heb je nog de poeder brandblusser. Deze is niet gelijk, maar is wel verwant aan de brandblussers.

Ik wil graag alle gelijke tags samenvoegen tot één tag en de verwante tags wil ik aan elkaar koppelen.

Mijn eerste stap is om de tags in de database op te slaan. Ik sla de naam op en bereken de metaphone en soundex van elke tag. De soundex ga ik denk ik laten vallen want die is tot nu toe nog niet bruikbaar gebleken voor mij. Het was ook een experiment voor mij, daar ik beide functies nog niet gebruikt had.

PHP:

$qs = $db->prepare('INSERT INTO tags SET name = :name, metaphone = :metaphone, soundex = :soundex');

$db->beginTransaction();

foreach($tags as $tag)
{
    $metaphone = metaphone($tag->name);
    $soundex = soundex($tag->name);
    $qs->bindParam(':name', $tag->name, PDO::PARAM_STR);
    $qs->bindParam(':metaphone', $metaphone, PDO::PARAM_STR);
    $qs->bindParam(':soundex', $soundex, PDO::PARAM_STR);
    $qs->execute();
}

$db->commit();

Dit proces duurt rond de 330 seconden.

Hierna haal ik alles weer op uit de database en ga ik beginnen met het vergelijken.

PHP:

$qs = $db->prepare('SELECT name FROM tags');
$qs->execute();
while($result = $qs->fetch(PDO::FETCH_ASSOC))
{
    $rowsA[] = $result['name'];
    $rowsB[] = $result['name'];
}

$qs = $db->prepare('INSERT INTO tagsMatches SET nameA = :nameA, nameB = :nameB, similarText = :similarText, levenshtein = :levenshtein, similarPhone = :similarPhone');

$db->beginTransaction();

foreach($rowsA as $rowA)
{
    foreach($rowsB as $rowB)
    {
        if($rowB !== $rowA)
        {
            $levenshtein = levenshtein($rowA, $rowB);
            similar_text($rowA, $rowB, $similarText);
            similar_text(metaphone($rowA), metaphone($rowB), $similarPhone);
            if($similarText > 80 || $similarPhone > 80)
            {
                $qs->bindParam(':nameA',$rowA,PDO::PARAM_STR);
                $qs->bindParam(':nameB',$rowB,PDO::PARAM_STR);
                $qs->bindParam(':similarText',$similarText,PDO::PARAM_STR);
                $qs->bindParam(':similarPhone',$similarPhone,PDO::PARAM_STR);
                $qs->bindParam(':levenshtein',$levenshtein,PDO::PARAM_INT);
                $qs->execute();
            }
        }
    }
}

$db->commit();

Ik bereken met levenshtein het aantal karakters dat verschilt.
Met een similar_text op de tag bereken ik het percentage waarin twee tags hetzelfde zijn. Dit gaf mij nog teveel verkeerde resultaten en toen ben ik ook de metaphone met similar_text gaan vergelijken. De tags die bij de naam of metaphone vergelijking meer dan 80% overeenkomen sla ik op in de database. Nu heb ik in de database al behoorlijk wat accurate koppelingen kunnen leggen tussen verschillende tags.
Wanneer beide similar_text waardes boven de 90% zitten en de levenshtein waarde zich onder de drie bevind zijn de tags meestal nagenoeg hetzelfde en kan ik deze dus als één en dezelfde zien.

Voor verwante tags aan een tag haal ik tien tags op met het hoogste gemiddelde van de twee similar_text waardes. Met deze actie koppel ik bijvoorbeeld astrologieboeken aan kookboeken, woordenboeken, leesboeken, etc... Over het algemeen kloppen de verwante tags op deze manier vrij aardig. Maar hier en daar staan er ook hele verkeerde combinaties tussen.

Alleen mijn probleem is dat de actie met de vergelijkingen veel te lang duurt met 20.000 tags (ik heb geen exacte waarde want mijn script wordt niet afgemaakt.
Aan het begin van mijn script het volgende geplaatst:

PHP:

ini_set('max_execution_time', 1800);
set_time_limit(1800);

Maar deze waarde wordt niet geaccepteerd door de server denk ik. Als ik hem op 900 zet krijg ik nog timeout error te zien. Hierna niet meer.

Zoals je mogelijk uit mijn code kan opmaken verschijnen er records dubbel in mijn database omdat ik een foreach loop gebruik in een foreach loop door dezelfde array. Stel ik heb array(a,b,c,d,e) en ik vergelijk de waardes uit die array met elkaar en ze voldoen aan mijn eisen dan krijg ik de records:

• a - b
• a - c
• a - d
• a - e
• b - a
• b - c
• b - d
• b - e
• c - a
• c - b
• c - d
• c - e
• d - a
• d - b
• d - c
• d - e
• e - a
• e - b
• e - c
• e - d

De vergelijking tussen a en b wordt weggeschreven, maar ook de vergelijking tussen b en a. Die zijn hetzelfde en wil ik dus maar eenmalig vergelijken en in mijn database schrijven.

In mijn database gaan kijken of elke vergelijking al gedaan is, zal denk ik alleen nog meer recourses kosten dan de vergelijkingen gewoon uitvoeren.

Heeft iemand een idee hoe ik nu kan zorgen dat elke vergelijking eenmalig gebeurd? En of er een betere manier is om de waardes met elkaar te vergelijken dan een foreach loop in een foreach loop.
Overigens sla ik nu nog de tagnamen op in de tabel tagsMatches, maar dit zullen de id's van mijn tags gaan worden.

En misschien is er een betere programmeertaal om de strings te vergelijken met elkaar, weet iemand dit? Heb ooit wel een wat in java en c# gedaan, maar mijn kennis daarvan is erg ver weggezakt ben ik bang. Maar wil graag een andere taal leren als dat hiervoor nuttig is.

[pedorus]

Dit klinkt als een eenmalig proces, dus ik zou zeggen, maak even wel een inschatting van hoe lang dit duurt in totaal, en splits het op in taken die wel te draaien zijn (en voer die uit). Als dit toch lastig is, dan zou ik even de tags database downloaden, het lokaal uitvoeren met php op de commandline, en weer uploaden.

Als de totale tijd echt te groot is, dan zou je alsnog met bijv. c# iets kunnen doen. (Met bijv. linq is dit nml vrij simpel volgens mij.) Ook zou je evaluatie slimmer kunnen doen, door alleen door te gaan voor gevallen die veelbelovend zijn. Dit lijkt mij echter onwaarschijnlijk bij 20.000 tags.

[Donderpoes]

Voor bestaande combinaties van tags is het inderdaad een eenmalig proces, maar theoretisch is het mogelijk dat ik elke dag 10.000 nieuwe tags ga ontvangen. In de praktijk zal dit een veel kleiner nummer zijn.

Opdelen van het proces is zo'n gek idee nog niet, maar dan moet ik denk ik toch nog eerst een optimalisatie doen betreffende welke tags wel niet vergelijken en opslaan. Een proces kan ik natuurlijk opdelen zodat elk deelproces op tijd klaar is. Maar ik blijf dan nog steeds zitten met dubbel opgeslagen data in mijn database.

Doorgaan met gevallen die veelbelovend zijn is een goede. Maar dit is iets nieuws wat opgezet wordt, een groot gedeelte van de tags zullen weinig tot niet gebruikt worden door bezoekers, maar ik weet nu nog niet welke wel en niet veel gebruikt zullen worden. Ik zou, zodra ik praktijk data heb, op de metaphone kunnen vergelijken van veel gebruikte tags en als ze dan de 75% halen met de tag verder kunnen gaan.

Overigens zullen de tags hoofdzakelijk de navigatie gaan vormen i.c.m. een zoekfunctie. Daarom is het van belang om zoveel mogelijk de gelijke en verwante tags bij elkaar te stoppen. Zou een beetje lullig zijn als ik van bezoekers vraag om een keuze te maken uit 20.000 menu items