Laden...

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

Erstellt von Serilla vor 4 Jahren Letzter Beitrag vor 4 Jahren 1.662 Views
S
Serilla Themenstarter:in
3 Beiträge seit 2019
vor 4 Jahren
Liste mit Wörtern erstellen, die mit ersten Zeichen der Suche übereinstimmen

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; } }
        }
    }
    
}

A
764 Beiträge seit 2007
vor 4 Jahren

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

4.931 Beiträge seit 2008
vor 4 Jahren

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)

S
Serilla Themenstarter:in
3 Beiträge seit 2019
vor 4 Jahren

Vielen Dank! Klappt hervorragend!

S
Serilla Themenstarter:in
3 Beiträge seit 2019
vor 4 Jahren

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; } }
        }
    }
}

4.931 Beiträge seit 2008
vor 4 Jahren

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).

A
764 Beiträge seit 2007
vor 4 Jahren

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

3.170 Beiträge seit 2006
vor 4 Jahren

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