Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

Liste mit Wörtern erstellen, die mit ersten Zeichen der Suche übereinstimmen
Serilla
myCSharp.de - Member



Dabei seit:
Beiträge: 3

Themenstarter:

Liste mit Wörtern erstellen, die mit ersten Zeichen der Suche übereinstimmen

beantworten | zitieren | melden

Hallo miteinander,

ich möchte einen Prefix Tree erstellen, der mir bei einer Suche eine Liste mit Wörtern ausgibt, die mit den ersten Zeichen der Suche übereinstimmen.

Mein Problem ist, dass ich bei meiner Suche nur ein "Trees.PrefixTree+d__5" erhalte und keine Liste mit Wörtern (der Array "dictionary" ist als Beispiel gedacht) und ich verstehe nicht warum. Kann mir jemand weiterhelfen?

Vielen Dank!


using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Threading;



namespace Trees
{
    
    public class Program
    {
        public static void Main()
        {
            
            //String[] file = File.ReadAllLines(@"C:\Users\samue\Desktop\Neuer Ordner (2)\liste.txt");
         
            
            string[] dictionary = new string[] { "test", "try", "angle", "the", "code", "is", "isnt" };
            PrefixTree trie = new PrefixTree();

            var stopwatch = new Stopwatch();

            foreach (var word in dictionary)
            {
                trie.Add(word);
            }

            //Thread workerThread = new Thread(trie.Search(suchwort);

            Console.WriteLine("Bitte geben Sie Ihren Suchbegriff ein:");
            string suchwort = Console.ReadLine();
            Console.WriteLine("Suchergebnis:");
            Console.WriteLine(trie.Search("te"));
        }
    }
    
    public class PrefixTree
    {
        private PrefixTreeNode root;

        public PrefixTree()
        {
            root = new PrefixTreeNode(String.Empty);
        }

        public void Add(string word)
        {
            AddRecursive(root, word, String.Empty);
        }

        private void AddRecursive(PrefixTreeNode node, string remainingString, string currentString)
        {
            if (remainingString.Length ≤ 0)
            {
                return;
            }

            char prefix = remainingString[0];
            string substring = remainingString.Substring(1);
            if (!node.SubNodes.ContainsKey(prefix))
            {
                node.SubNodes.Add(prefix, new PrefixTreeNode(currentString + prefix));
            }

            if (substring.Length == 0)
            {
                node.SubNodes[prefix].IsWord = true;
                return;
            }
            else
            {
                AddRecursive(node.SubNodes[prefix], substring, currentString + prefix);
            }
        }
        

        public IEnumerable<string> Search(string searchString)
        {
            PrefixTreeNode node = root;
            foreach (var search in searchString)
            {
                if (!node.SubNodes.ContainsKey(search))
                {
                    return new string[0];
                }
                node = node.SubNodes[search];
            }

            return FindAllWordsRecursive(node);
        }

        private IEnumerable<string> FindAllWordsRecursive(PrefixTreeNode node)
        {
            if (node.IsWord)
            {
                yield return node.Word;
            }

            foreach (var subnode in node.SubNodes)
            {
                foreach (var result in FindAllWordsRecursive(subnode.Value))
                {
                    yield return result;
                }
            }
        }

        protected class PrefixTreeNode
        {
            private readonly Dictionary<char, PrefixTreeNode> subNodes;
            private bool isWord;
            private readonly string word;

            public PrefixTreeNode(string word)
            {
                subNodes = new Dictionary<char, PrefixTreeNode>();
                isWord = false;
                this.word = word;
            }

            public Dictionary<char, PrefixTreeNode> SubNodes { get { return subNodes; } }
            public bool IsWord { get { return isWord; } set { isWord = value; } }
            public string Word { get { return word; } }
        }
    }
    
}
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Serilla am .
private Nachricht | Beiträge des Benutzers
Alf Ator
myCSharp.de - Member



Dabei seit:
Beiträge: 631

beantworten | zitieren | melden

Hallo Serilla


Search(..) gibt ein IEnumerable<string> zurück. Console.WriteLine(..) erwartet aber einen string.
Versuchmal aus dem Rückgabewert von Search einen String zu machen.

Z.B. mit string.Join(...)

Gruß
Alf
private Nachricht | Beiträge des Benutzers
Th69
myCSharp.de - Experte

Avatar #avatar-2578.jpg


Dabei seit:
Beiträge: 4001

beantworten | zitieren | melden

Hallo und willkommen,

du gibst ja bei der Search-Methode ein IEnumerable<string> zurück (also quasi eine Liste), gibst diese aber direkt per Console.WriteLine aus, so daß einfach dessen ToString()-Methode aufgerufen wird (die standardmäßig den Datentypnamen ausgibt).
Du mußt die Strings einzeln in einer Schleife ausgeben:


foreach (string s in trie.Search("te"))
    Console.WriteLine(s);
(oder alternativ z.B. String.Join(...) benutzen)
private Nachricht | Beiträge des Benutzers
Serilla
myCSharp.de - Member



Dabei seit:
Beiträge: 3

Themenstarter:

beantworten | zitieren | melden

Vielen Dank! Klappt hervorragend!
private Nachricht | Beiträge des Benutzers
Serilla
myCSharp.de - Member



Dabei seit:
Beiträge: 3

Themenstarter:

beantworten | zitieren | melden

Wenn ich versuche den obigen Code mit Multitasking starte, bekomme ich keine Rückgabe. Weiß jemand warum?


using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Threading.Tasks;



namespace Trees
{
    
    public class Program
    {
        public static void Main()
        {
            
            String[] file = File.ReadAllLines(@"C:\Users\samue\Desktop\Neuer Ordner (2)\liste.txt");
            //string[] dictionary = new string[] { "test", "try", "angle", "the", "code", "is", "isnt" };

            PrefixTree trie = new PrefixTree();

            var sw = new Stopwatch();
            foreach (var word in file)
            {
                trie.Add(word);
            }
                        
            Task.Run(() => trie.Suche());

        }
    }
    
    public class PrefixTree
    {
        private PrefixTreeNode root;

        public PrefixTree()
        {
            root = new PrefixTreeNode(String.Empty);
        }

        //Rekursives Einfügen der Worte
        public void Add(string word)
        {
            AddRecursive(root, word, String.Empty);
        }

        private void AddRecursive(PrefixTreeNode node, string remainingString, string currentString)
        {
            if (remainingString.Length ≤ 0)
            {
                return;
            }

            char prefix = remainingString[0];
            string substring = remainingString.Substring(1);
            if (!node.SubNodes.ContainsKey(prefix))
            {
                node.SubNodes.Add(prefix, new PrefixTreeNode(currentString + prefix));
            }

            if (substring.Length == 0)
            {
                node.SubNodes[prefix].IsWord = true;
                return;
            }
            else
            {
                AddRecursive(node.SubNodes[prefix], substring, currentString + prefix);
            }
        }

        public void Suche()
        {
            PrefixTree trie = new PrefixTree();
            var sw = new Stopwatch();
            Console.WriteLine("Bitte geben Sie Ihren Suchbegriff ein:");
            string suchwort = Console.ReadLine();
            Console.WriteLine("Suchergebnis:");
            sw.Start();
            Console.WriteLine(string.Join(", ", trie.Search(suchwort)));
            sw.Stop();
            Console.WriteLine("Laufzeit der Suche" + sw.Elapsed);

        }
        //Rekursive Suche nach vollständiger Wortliste bei gegebenem Prefix
        public IEnumerable<string> Search(string searchString)
        {
            Console.WriteLine("Task gestartet");
            PrefixTreeNode node = root;
            foreach (var search in searchString)
            {
                if (!node.SubNodes.ContainsKey(search))
                {
                    return new string[0];
                }
                node = node.SubNodes[search];
            }
            var result = FindAllWordsRecursive(node);
            Console.WriteLine(string.Join(", ", result));
            return FindAllWordsRecursive(node);
        }

        private IEnumerable<string> FindAllWordsRecursive(PrefixTreeNode node)
        {
            if (node.IsWord)
            {
                yield return node.Word;
            }

            foreach (var subnode in node.SubNodes)
            {
                foreach (var result in FindAllWordsRecursive(subnode.Value))
                {
                    yield return result;
                }
            }
        }

        protected class PrefixTreeNode
        {
            private readonly Dictionary<char, PrefixTreeNode> subNodes;
            private bool isWord;
            private readonly string word;

            public PrefixTreeNode(string word)
            {
                subNodes = new Dictionary<char, PrefixTreeNode>();
                isWord = false;
                this.word = word;
            }

            public Dictionary<char, PrefixTreeNode> SubNodes { get { return subNodes; } }
            public bool IsWord { get { return isWord; } set { isWord = value; } }
            public string Word { get { return word; } }
        }
    }
}
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Serilla am .
private Nachricht | Beiträge des Benutzers
Th69
myCSharp.de - Experte

Avatar #avatar-2578.jpg


Dabei seit:
Beiträge: 4001

beantworten | zitieren | melden

Durch das "Task.Run(() => trie.Suche());" startest du zwar einen neuen Task, aber weil danach die Main-Methode zu Ende ist, beendet sich das gesamte Programm sofort.

Was bezweckst du denn mit dem Multi-Tasking konkret (denn bisher macht dein Programm ja nichts anderes als die Suche zu starten)?

Ansonsten s.a. [Artikel] Multi-Threaded Programmierung sowie weitere Tutorials im Netz über Multi-Tasking (Task, async, await).
private Nachricht | Beiträge des Benutzers
Alf Ator
myCSharp.de - Member



Dabei seit:
Beiträge: 631

beantworten | zitieren | melden

Als Quickfix hilft möglicherweise ein Console.ReadLine() am Ende.

Richtiger wäre es dann die Methode Search mit dem async-Keyword auszustatten und mit dem Rückgabewert (z.B. Task<IEnumerable<string>>) zu arbeiten.
Consolen-Ausgaben (wie alle UI-Geschichten) laufen dann nicht in einem Task, sondern im Mainthread.

Absehen davon schau dir noch mal das an: Wie poste ich richtig?
Das hilft im Forum die Übersicht zu bewahren.

Gruß
Alf
private Nachricht | Beiträge des Benutzers
MarsStein
myCSharp.de - Experte

Avatar #avatar-3191.gif


Dabei seit:
Beiträge: 3429
Herkunft: Trier -> München

beantworten | zitieren | melden

Hallo,

hinzu kommt noch, dass Du in Deiner Suche()-Methode eine neue Instanz von PrefixTree erstellst, auf der Du dann weiterarbeitest.
Diese Instanz kennt aber die in der Main-Methode hinzugefügten Wörter nicht...

Gruß, MarsStein
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
private Nachricht | Beiträge des Benutzers