[php] Strings groeperen op gelijkenis

[Verwijderd]

Ik ben een parser aan het schrijven voor chatlogs. Ik wil de inhoud van mijn chatlogs netjes in een database wegschrijven en ze zo makkelijk en snel kunnen doorzoeken of analyseren. Op het moment ben ik bezig met een parser voor de XML bestanden die Windows Live Messenger maakt. Het probleem met deze logs is dat bij berichten enkel de nicknames van de zender en de ontvanger worden opgeslagen, en verder geen enkele methode van identificatie.
Voorbeeld van een bericht:

XML:

<Message Date="22-1-2007" Time="11:43:43" DateTime="2007-01-22T10:43:43.546Z" SessionID="1">
  <From><User FriendlyName="Kay"/></From>
  <To><User FriendlyName="Joyce...        Toetsweek  [0/11]     ×"/></To>
  <Text Style="font-family:MS Shell Dlg; color:#000000; ">goedemorgen! :)</Text>
</Message>

Het punt is dat die nicknames door de log heen kunnen veranderen. Uit die log haal ik de unieke nicknames (de keys van de nicknames in deze array worden aan de berichten gekoppeld):

code:

Array
(
    [0] => Kay
    [1] => Joyce...        Toetsweek  [0/11]     ×
    [2] => Joyce...        om 12 uur gaan we starten!     Toetsweek  [0/11]     ×
    [3] => Joyce...           Toetsweek  [0/11]     ×
)

Nu wil ik deze nicknames grouperen op gelijkenis. Ik heb al een stukje code die van de bovenstaande nicknames een leesbaarder array geeft:

code:

Array
(
    [0] => kay
    [1] => joyce
    [2] => joyce
    [3] => joyce
)

Nu zit ik echter vast op hoe ik deze nicknames kan grouperen op gelijkenis. In dit geval zijn ze na mijn bewerking allemaal gelijk, maar dit hoeft niet altijd zo te zijn, er kan makkelijk een kleine variatie inzitten.
Ik heb de functie Levehnstein al gevonden, maar geen idee hoe ik met die scores netjes kan grouperen. Ik haal met de volgende code een array met de scores op:

PHP:

for($x = 0; $x < count($nicks); $x++)
    for($y = 0; $y < count($nicks); $y++)
        if($x != $y
        && !isset($scores[$y][$x]))
            $scores[$x][$y] = levenshtein($nicks[$x],$nicks[$y]);

Dit levert al een (na sorteren met asort()) prima array op:

code:

Array
(
    [2] => Array
        (
            [3] => 0
        )
    [1] => Array
        (
            [2] => 0
            [3] => 0
        )
    [0] => Array
        (
            [1] => 4
            [2] => 4
            [3] => 4
        )
)

Maar hier zit ik vast. Hoe ga ik van deze gegevens naar een array met 2 (of meer) elementen waarin alle gelijkende nicknames bij elkaar staan?
Zoiets dus:

code:

Array
(
    [0] => Array
        (
            [0] => 0 // kay
        )
    [1] => Array
        (
            [0] => 1 // joyce
            [1] => 2 // joyce
            [2] => 3 // joyce
        )
)

Waarschijnlijk is het heel gemakkelijk en zie ik wat over het hoofd, maar ik kom er niet uit.

[ Voor 5% gewijzigd door Verwijderd op 23-01-2007 10:38 ]

[djc]

Volgens mij is het nog niet zo makkelijk, en is dat omdat je wilt clusteren. Het probleem daarvan is dat je dus eigenlijk niet alleen wil weten hoe een nick zich verhoudt tot een van de andere nicks, maar hoe de nick zich verhoudt tot een groepje van andere nicks. Dat maakt het probleem redelijk complex.

[NMe]

Manuzhai schreef op dinsdag 23 januari 2007 @ 11:40:
Volgens mij is het nog niet zo makkelijk, en is dat omdat je wilt clusteren. Het probleem daarvan is dat je dus eigenlijk niet alleen wil weten hoe een nick zich verhoudt tot een van de andere nicks, maar hoe de nick zich verhoudt tot een groepje van andere nicks. Dat maakt het probleem redelijk complex.

Waarom? Gewoon een loopstructuur en levenshtein toepassen zoals hierboven en het zaakje in een multidimensionaal array opslaan zodat je de onderlinge verschillen tussen nicks weet. Vervolgens kun je met usort zelf een functie maken die het zaakje sorteert in een nieuw array. Lijkt me op zich niet zo'n lastig probleem?

Als a op b lijkt, en b op c, dan lijkt a (in enige mate) ook op c, dus dat lijkt me het probleem ook niet.

[ Voor 7% gewijzigd door NMe op 23-01-2007 12:27 ]

[Verwijderd]

Ik ben eruit , het was idd niet zo heel moeilijk. Het enige nadeel is dat alle 'nieuwe' nicks alleen worden vergeleken met de eerste nicks die in de groepen staan, maar ik een sluitende oplossing lukt toch niet, dus ik denk dat alles toch even met de hand gecheckt moet worden. Mijn oplossing:

PHP:

$groupedNicks = array();
foreach($parsedNicks as $nickIndex => $nick)
{
    $newGroup = true;
    foreach($groupedNicks as $groupIndex => $groupedNick)
        if(levenshtein($groupedNick['str'],$nick) < 2)
        {
            $groupedNicks[$groupIndex]['alike'][] = $nickIndex;
            $newGroup = false;
            break;
        }

    if($newGroup)
    {
        $idx = count($groupedNicks);
        $groupedNicks[$idx]['str'] = $nick;
        $groupedNicks[$idx]['alike'][] = $nickIndex;
    }
}