Algoritme til at finde det ord som ligner mest..

Du kan godt lave noget kode som finder noget der ligner.

Men da det er svært at definere "ligner" præcist, så er det ikke
sikkert at du får de resultater du gerne vil have.

Den mest kendte algoritme er SoundEx.

For noget C# SoundEx kode se:

http://www.thecodeproject.com/csharp/soundex.asp

Fik du løst det? Ellers vil jeg da godt give et bud - det skal bare omsættes til kode.

Ud fra det eks. du selv giver, ser det ud til at du kan bruge følgende fremgangsmåde:

<pseudo-pseudo-kode>

Definationer:

"hele ord" er whitespace-terminarede char kombinationer som eks "dette", "er", "et", "ord" i strengen "dette er et ord".

karakterer er enkelte tegn. eks 'f' eller 'u'.

strenge er et punkt i en liste, eks "FC Århus".

Kode:

For hver streng i den liste der søges i:
{
Hele_ord = Tæl antal "hele ord" som matcher. (eks.: "ord" og "ORD")

Forkortelser = antal "hele ord" der enten har alle chars fra et ord i den anden liste, eller hvor et ord i den anden liste har alle chars fra dette ord. (eks.: "CPH" og "CoPenHagen")

}

Den streng med flest (hele_ord + forkortelser) er bedste match.

En udbygning kunne være at ændre (hele_ord + forkortelser) til (hele_ord * hel_ords_vægt + forkortelser * forkortelses_vægt) så du kan justere om hele ord eller forkortelser skal veje tungest.
Man kunne også vælge at tælle antal uens tegn, eller ord der ikke er pladseret samme sted, for at kunne udelukke evt. resultater hvor der er flere strenge som matcher lige godt.

--

Alternativet til denne traditionelle måde at gøre det på - som jeg ser det - er at lade en genetisk algoritme om at finde den bedste måde at udføre matchningen på, eller evt. træne et simpelt neuralt netværk til at genkende de bedste matches. Det er godt nok lidt at skyde gråspurve med kanonkugler, men kan muligvis være den eneste brugbare løsning hvis opgaven er bare en tand mere kompliceret end det du her beskriver.
Mere om neurale netværk på: http://www2000198.thinkquest.dk/

Hej Lemon - Jeg har lige et spørgsmål - Ville alle nedenstående kunne genkendes med din pseudo-kode?
    Tottenham - Tottenham Hotspur       
    Liverpool - FC Liverpool   
    Chelsea    FC - Chelsea       
    Man Utd    - Manchester Utd       
    Hertha BSC Berlin - Hertha Berlin       
    West Brom - West Bromwich   
    Hannover 96 - Hannover       
    1. FC Kaiserslautern - Kaiserslautern       
    Man City - Manchester City       
    Borussia Mgladbach - Bor. M´Gladbach       
    1. FC Nürnberg - Nürnberg       
    FSV Mainz -Mainz

Yup, de ville alle kunne genkendes - samt nedenstående:
  T.H. - Trine H.
  McD - McDonalds

Jeg skal forresten også selv bruge noget lignende, så jeg kan lige lave en simpel stump kode.

Det er da pænt af dig... Er det klar idag :)

using System;

namespace NameSearch
{
    class TestClass
    {
        static void Main(string[] args)
        {
            string searchFor = "Man Utd";
            string[] searchIn = "Tottenham Hotspur;FC Liverpool;Chelsea;Manchester United;Hertha Berlin;West Bromwich;Hannover;Kaiserslautern;Manchester City;Bor. M´Gladbach;Nürnberg;Mainz".Split(';');
            int best = BestMatch(searchFor, searchIn);
            if(best == -1)
                Console.WriteLine("Intet fundet.");
            else
                Console.WriteLine("'" + searchFor + "' ligner sjovt nok '" + searchIn[best] + "'.");

            Console.WriteLine("\n\n\t** Kan du ramme enter? aká Hit enter to quit **");
            Console.ReadLine();
        }

        /// <summary>
        /// Matcher navne ol. som eks:
        ///  Tottenham - Tottenham Hotspur       
        ///  Liverpool - FC Liverpool
        ///  Chelsea    FC - Chelsea
        /// 
        /// Returnerer: indeks i nameList på det bedste match, eller -1 hvis der ikke blev fundet et match.
        /// </summary>
        /// <param name="name">Det navn eller den forkortelse der skal søges efter.</param>
        /// <param name="nameList">Den liste af navne og forkortelser der skal søges i.</param>
        /// <returns></returns>
        static int BestMatch(string name, string[] nameList)
        {
            string WhiteSpacesAndSutch = "\t .,-_'´`|()\"@/\\\r\n*[]{}$&+?="; /* Dette er de tegn som deler ord. Kan tilføjes/fjernes efter behov.
                                                                                * Eks.: Hvis # bliver brugt ved eks "Hansensvej#7", så tilføj # til denne liste.
                                                                                */
            int wordMatch, innerInitialsMatch;
            int[] matchWeights = new int[nameList.Length];
            int listIdx, aNameIdx, bNameIdx, aCharIdx, bCharIdx;
            string[] nameTmp, listTmp;

            nameTmp = name.ToLower().Split(WhiteSpacesAndSutch.ToCharArray());
            for(listIdx = 0; listIdx < nameList.Length; listIdx++)
            {
                wordMatch = 0;
                innerInitialsMatch = 0;
                listTmp = nameList[listIdx].ToLower().Split(WhiteSpacesAndSutch.ToCharArray());
                for(aNameIdx = 0; aNameIdx < nameTmp.Length; aNameIdx++)
                {
                    for(bNameIdx = 0; bNameIdx < listTmp.Length; bNameIdx++)
                    {
                        if(nameTmp[aNameIdx].Length != 0 && listTmp[bNameIdx].Length != 0)
                        {
                            if(nameTmp[aNameIdx] == listTmp[bNameIdx]) // Check for ens ord:
                                wordMatch++;
                            else // Check for forkortelser
                            {
                                if(nameTmp[aNameIdx].Length > listTmp[bNameIdx].Length) // Check om listeordet er en del af søgeordet
                                {
                                    bCharIdx = 0;
                                    for(aCharIdx = 0; aCharIdx < nameTmp[aNameIdx].Length; aCharIdx++)
                                    {
                                        if(nameTmp[aNameIdx][aCharIdx] == listTmp[bNameIdx][bCharIdx])
                                            bCharIdx++;
                                        if(bCharIdx == listTmp[bNameIdx].Length)
                                            break; // Liste slut - forkortelse fundet.
                                    }
                                    if(bCharIdx == listTmp[bNameIdx].Length)
                                        innerInitialsMatch++;
                                }
                                else if(nameTmp[aNameIdx].Length < listTmp[bNameIdx].Length) // Check om søgeeordet er en del af listeordet
                                {
                                    aCharIdx = 0;
                                    for(bCharIdx = 0; bCharIdx < listTmp[bNameIdx].Length; bCharIdx++)
                                    {
                                        if(listTmp[bNameIdx][bCharIdx] == nameTmp[aNameIdx][aCharIdx])
                                            aCharIdx++;
                                        if(aCharIdx == nameTmp[aNameIdx].Length)
                                            break; // Ord slut - forkortelse fundet.
                                    }
                                    if(aCharIdx == nameTmp[aNameIdx].Length)
                                        innerInitialsMatch++;
                                }
                            }
                        }
                    }
                }
                matchWeights[listIdx] = wordMatch + innerInitialsMatch;
            }

            int bestMatchWeight, bestMatchIdx;
            bestMatchIdx = -1;
            bestMatchWeight = 0;
            for(listIdx = 0; listIdx < matchWeights.Length; listIdx++)
            {
                if(bestMatchWeight < matchWeights[listIdx])
                {
                    bestMatchIdx = listIdx;
                    bestMatchWeight = matchWeights[listIdx];
                }
            }

            return bestMatchIdx;
        }
    }
}

Du skal nok smide det i en try{} catch{} i starten - for jeg har ikke debugget det - og svigermor sad ved siden af min og snakkede mens jeg kodede det. ;o)

string searchFor = "Man Utd";
            string[] searchIn = "Tottenham Hotspur;FC Liverpool;Chelsea;Manchester United;Hertha Berlin;West Bromwich;Hannover;Kaiserslautern;Manchester City;Bor. M´Gladbach;Nürnberg;Mainz".Split(';');
try
{
            int best = BestMatch(searchFor, searchIn);
}
catch(Exception ex)
{
    Console.WriteLine("Æv, der opstod en fejl. Men  det kan heldigvis rettes.\r\n" + ex.ToString();
}
            if(best == -1)
                Console.WriteLine("Intet fundet.");
            else
                Console.WriteLine("'" + searchFor + "' ligner sjovt nok '" + searchIn[best] + "'.");

Med andre ord: Tilbagemelt lige evt. fejl du måtte løbe på - samt de benyttede inputs som skabte fejlen, så jeg kan rette det. Finder jeg selv fejl poster jeg lige rettelserne her.

det er bare super ... Tester det lige...

1. FC Kaiserslautern bliver til FC Liverpool... Kan den slags fejl undgås??

er du der?

Ja jeg ser lige på det idag.

Hej lemon, har du fået kigget lidt på det endnu :)

Yup, men åbenbart ikke nok ;) Jeg har lige noget c++ kode som skal værefærdig asap, så kigger jeg på det bagefter, enten imorgen eller i weekenden.

oki - glæder mig til at se resultatet :)

Glæder mig stadig til resultatet :) men du har nok travlt...

Ja sorry, det er helt rigtigt gættet at jeg har ustyrligt travlt, men jeg ser på det så snart jeg kan. Håber du har tid/tålmodighed til det.

using System;

public class NameMatcher
{
    private static int Score(string s1, string s2)
    {
        string[] w1 = s1.Split(" ".ToCharArray());
        string[] w2 = s2.Split(" ".ToCharArray());
        int score = 0;
        for(int i = 0; i < w1.Length; i++)
        {
            for(int j = 0; j < w2.Length; j++)
            {
                if(w1[i] == w2[j])
                {
                    score += 4*w1[i].Length;
                }
                else if(w1[i].IndexOf(w2[j])==0)
                {
                    score += 4*w2[j].Length;
                }
                else if(w2[j].IndexOf(w1[i])==0)
                {
                    score += 4*w1[i].Length;
                }
                else
                {
                    int front = 0;
                    while(front < w1[i].Length && front < w2[j].Length && w1[i][front] == w2[j][front]) {
                        front++;
                    }
                    score += 2*front;
                    int back = 0;
                    while(back < w1[i].Length && back < w2[j].Length && w1[i][w1[i].Length-back-1] == w2[j][w2[j].Length-back-1]) {
                        back++;
                    }
                    score += back;
                }
            }
        }
        return score;
    }
    public static string BestMatch(string s, string[] possible) {
        int ix = -1;
        int maxscore = -1;
        for(int i = 0; i < possible.Length; i++)
        {
            int score = Score(s.ToUpper(), possible[i].ToUpper());
            if(score > maxscore)
            {
                ix = i;
                maxscore = score;
            }
        }
        if(maxscore > 0)
        {
            return possible[ix];
        }
        else
        {
            return "(unknown)";
        }
    }
}

class MainClass
{
    public static void Main(string[] args)
    {
        string[] name1 = { "FC Copenhagen",
                          "Århus FC",
                          "Tottenham Hotspur",
                          "FC Liverpool",
                          "Chelsea",
                          "Manchester Utd",
                          "Hertha Berlin",
                          "West Bromwich ",
                          "Hannover",
                          "Kaiserslautern",
                          "Manchester City",
                          "Bor. M´Gladbach",
                          "Nürnberg",
                          "Mainz" };
        string[] name2 = { "FC CPH",
                          "FC Århus",
                          "Tottenham",
                          "Liverpool",
                          "Chelsea FC",
                          "Man Utd",
                          "Hertha BSC Berlin",
                          "West Brom",
                          "Hannover 96",
                          "1. FC Kaiserslautern",
                          "Man City",
                          "Borussia Mgladbach",
                          "1. FC Nürnberg",
                          "FSV Mainz" };
        for(int i = 0; i < name2.Length; i++)
        {
            Console.WriteLine(name2[i] + " = " + NameMatcher.BestMatch(name2[i], name1));
        }
        for(int i = 0; i < name1.Length; i++)
        {
            Console.WriteLine(name1[i] + " = " + NameMatcher.BestMatch(name1[i], name2));
        }
    }
}

FC CPH = FC Copenhagen
FC Århus = Århus FC
Tottenham = Tottenham Hotspur
Liverpool = FC Liverpool
Chelsea FC = Chelsea
Man Utd = Manchester Utd
Hertha BSC Berlin = Hertha Berlin
West Brom = West Bromwich
Hannover 96 = Hannover
1. FC Kaiserslautern = Kaiserslautern
Man City = Manchester City
Borussia Mgladbach = Bor. M'Gladbach
1. FC Nürnberg = Nürnberg
FSV Mainz = Mainz
FC Copenhagen = FC CPH
Århus FC = FC Århus
Tottenham Hotspur = Tottenham
FC Liverpool = Liverpool
Chelsea = Chelsea FC
Manchester Utd = Man Utd
Hertha Berlin = Hertha BSC Berlin
West Bromwich  = West Brom
Hannover = Hannover 96
Kaiserslautern = 1. FC Kaiserslautern
Manchester City = Man City
Bor. M'Gladbach = Borussia Mgladbach
Nürnberg = 1. FC Nürnberg
Mainz = FSV Mainz

Jeg har grebet det lidt anderledes an end lemon.

Arne - Jeg har prøvet med andre navne og jeg må sige at dit fungerer rigtig godt - Gider i lægge et svar så kan i dele pointene - og mange tak for hjælpen til jer begge...

ok

Argh, så glemte jeg selvfølgeligt alt om det her... nå men godt du fik løst det og til Arne: Lækker kode :)

Ok - men tak for hjælpen begge - Arne du får pointene