Dictionary problems-And the cause of a stackoverflow

I have a dictionary that looks like this. Please look at it very closely!


Field1 Field2
mainly|chiefly
mainly|fundamentally
mainly|typically
primarily|mainly
primarily|particularly
particularly|specifically
specifically|typically


Can you see how one word is used to replace another, then that word is replaced by another, then that by another? From what I've seen, this could be the source of an infinite loop or a stackoverflow. I tested my program with a small dictionary of names of upto 2000 records, and it worked without problems because each name was unique. The only problem I am having is that, when I use a different dictionary, the code is working 100% percent. I tested it by getting various words from different sections of the dictionary, and put them on my short wordlist, and it worked! There was no problems at all! Can you help with that? Maybe the code needs to be extended alot. The code is a grammar checker with a RichTextBox, a search button, and a contextMenu.

I have no clue as to the whys, what or hows of your code because you did not post it.

Just about all that can be said it that the list you have is not valid for a dictionary object. Each dictionary key must be unique and your list has duplicate keys.

Maybe you are using something completely different that a Dictionary object, who knows. You haven't provided any code.
kevin

Ok, check this one out:

Code:

---

Imports System.IO
Imports System
Imports System.Collections.Generic
Public Class Form1
    Dim checkWord As String
    Dim kamau As String
    Dim foundIndex As Integer
    Dim start As Integer = 0
    Private replacements As New Dictionary(Of String, List(Of String))

    Dim nextCheckIndex As Integer = 0

    Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load



        Using reader As New StreamReader("C:\Users\Acer\Desktop\Akaka7.txt")
            Do Until reader.EndOfStream
                Dim parts = reader.ReadLine().Split("|"c)

                If replacements.ContainsKey(parts(0)) Then
                    replacements(parts(0)).Add(parts(1))
                Else
                    Dim newWordList As New List(Of String)
                    newWordList.Add(parts(1))
                    replacements.Add(parts(0), newWordList)
                End If


            Loop
        End Using




        RichTextBox1.Text = "You provided a bad advice, irregardless of your intention. You provided a bad advice, irregardless of your intention. "
    End Sub
    Public Sub ContextMenuStrip1_ItemClicked(ByVal sender As Object, ByVal e As ToolStripItemClickedEventArgs) Handles ContextMenuStrip1.ItemClicked

        For Each Auto1 In replacements(checkWord)

            Auto1 = e.ClickedItem.Text
            kamau = Auto1
        Next

    End Sub
    Private Function GetWordWithOutBracketedText(SelectedReplacement As String) As String
        If Strings.InStr(SelectedReplacement, "(") = 0 Then
            Return SelectedReplacement
        End If
        Dim arr() As String = Strings.Split(SelectedReplacement, "(")
        Return arr(0)
    End Function   


    Private Sub CheckForReplacementText()
        Try
            checkWord = replacements.Keys.ElementAt(nextCheckIndex)

            foundIndex = RichTextBox1.Find(checkWord, start, RichTextBoxFinds.WholeWord)
            If foundIndex > -1 Then
                ContextMenuStrip1.Items.Clear()
                For Each replacement In replacements(checkWord)

                    ContextMenuStrip1.Items.Add(replacement, Nothing, Sub(sndr As Object, ea As EventArgs)
                                                                          RichTextBox1.SelectedText = GetWordWithOutBracketedText(kamau)
                                                                      End Sub)



                    ContextMenuStrip1.Show(RichTextBox1, RichTextBox1.GetPositionFromCharIndex(RichTextBox1.SelectionStart + RichTextBox1.SelectionLength))
                Next
            Else
                nextCheckIndex = nextCheckIndex + 1
                CheckForReplacementText()
            End If
        Catch e As Exception
            MessageBox.Show(e.ToString)
        End Try
    End Sub

    Private Sub BtnSearch_Click(sender As System.Object, e As System.EventArgs) Handles BtnSearch.Click
        CheckForReplacementText()
    End Sub

---

Quote:

---

the list you have is not valid for a dictionary object

---

He's not referring to the programming concept of a dictionary. He's actually referring to a list of words and possible replacements. More like a thesaurus really.

Quote:

---

this could be the source of an infinite loop or a stackoverflow.

---

It could depending on how you use it. I haven't read through your current code but if I remember your previous thread correctly you were allowing the user to select a single option from that list. In that case I don't think you would end up with an infinite loop because you're not in a loop in the first place. You're getting all the possible replacement once and allowing a single selection.

I'll spend a couple of minutes looking over your code now to make sure my understanding of whet you're doing is correct but I think you're OK.


Edit> I don't see you chaining your way through the dictionary so you should be safe from an infinite loop in that regard.

I am troubled by the fact that CheckForReplacementText recurses though (ie, it call itself). That will cause an infinite loop if you don't have a guaranteed exit condition. I think your exit is guaranteed, though, or at least it will throw an error before reaching infinite - nextCheckIndex will eventually exceed the size of the dictionary at which point your call to replacements.Keys.ElementAt(nextCheckIndex) will throw an ArgumentOutOfRangeException. So I don't think you'll get an infinite loop there either. It's certainly an area worth examining if you're getting problems, though.

Yes, I tried to implement the Psuedo code, but something went wrong along the way. I thought first, it was best to conduct some checks to see what was happening. When I tested different dictionaries, I found the clue. As soon as this is done, I will be able to implement the Psuedo code as planned. This is the most concerning area of concern:


I assume this could be because of an infinite loop caused by one word calling another, then that word calling another, then that one!

The solution will be to delete these duplicates that are in the second column that have now been put in the first column! For starters, I assume the program is working. I will first need to check if an item in the second column is added in the first column! Then, I should now be able to delete it, and the dictionary will be fine. The file is a Giant.

It's kind of up to you to handle what to do. There's a lot of different solutions that depend a lot on exactly how you do replacements.

I get how you get in this situation. The pseudocode is something like this;

Code:

---

For each word in the text:
    See if there is a replacement for the current word.
    Replace it.

---

The trick comes to how you break down "for each word". If you write it a certain way, you can end up checking the same word multiple times for replacement. Don't do that. Make sure you only do one replacement per word, then move on to the next word.

So long as you can prove you're only checking each word for replacement once, you won't have an infinite loop. In my opinion, it seems harder to write code that could have this problem than otherwise.

Sitten Spynne

So you suggest I Move Next? I have already done that, but I have a bit of code tacked somewhere to be used for my Pseudo code implementation. This is just a prototype stage. I will actually post the code for you, only that is doesn't Move Next as it was supposed, but worked on a dictionary (Of String, String).

Code:

---

    Public Function MoveNext() As Integer
        startZ = startindexZ + endindex
        If startindex >= replacements.ToString.Length Then
            Return False
        Else
            Return True
        End If

---

Quote:

---

I assume this could be because of an infinite loop caused by one word calling another, then that word calling another, then that one!

---

That wouldn't happen because you're working your way through the dictionary, not the text box, and you do the replacement in the text box.

• So the loop would find word A in the dictionary and look for it in the text box.
• It finds some instances of Word A and offers the user (amongst other things) word B as a replacement.
• The user picks Word B and all instance of word A in the text box get replaced with Word B (I think that's your intention but you haven't written the code to do that in your context menu click event yet)
• The loop then finds word B in the dictionary and looks for instances of it in the text box.
• It finds some, including the ones that used to be Word A, and offers the user (amongst other things) word A as a replacement.
• The user picks word A and you then replace Word B with word A in the text box.
• At this point anything that started out as Word A will be back to being Word A and anything that started out as word B will also be Word A
• Your recursive loop will now continue working it's way through the dictionary but it will not recheck Word A or Word B because it's already past them => no risk of an infinite loop.

You won't get an infinite loop because your looping the dictionary's keys collection and you're only checking each key once.

@Sitten - that's not actually what he's doing. If you look closer you'll see that he's actually doing a recursive loop through the words in the dictionary and checking to see if each one exists in the text box. If it's found he pops up a context menu with the possible replacements. The code to actually carry out the replacement isn't there yet but will, presumably, go in the context menu click event and will, presumably, replace all instances. It's hard to spot but check out his use of the nextCheckIndex variable and the fact that CheckForReplacementText recurses.

I am now doing the checks on a RichTextBox.

Dexter

Quote:

---

The user picks Word B and all instance of word A in the text box get replaced with Word B (I think that's your intention but you haven't written the code to do that in your context menu click event yet)

---

Here is the part that does that job.

Code:

---

  Public Sub ContextMenuStrip1_ItemClicked(ByVal sender As Object, ByVal e As ToolStripItemClickedEventArgs) Handles ContextMenuStrip1.ItemClicked

        For Each Auto1 In replacements(checkWord)

            Auto1 = e.ClickedItem.Text
            kamau = Auto1
        Next

    End Sub

---

Oh. I didn't think about it like FunkyDexter said, I was just sort of thinking through the problem without referencing the specific implementation. Here's what I think.

There's two ways to approach replacement like this. (Which, by the way, is more "thesaurus" than "dictionary".)

It seems like what you have is "For every word in my dictionary, I look for that word in the text, then replace it. So with a certain sequence of replacements, I might end up replacing the same words in sequence over and over again".

My hunch is that's still not true, unless every time you do a replacement you start iterating over the dictionary again. "For each word in the dictionary" will terminate. But I think it's the wrong order to go about things. Think about how many words will be in a "full" dictionary vs. how many words are in text. Most dictionaries are bigger than most books. So looping over "every possible replacement" for a 500 word text is going to be a monumental waste of time.

That's why my imagination conjured another way: loop over each word of the text, ask if it has a replacement in the dictionary. If so, append the replacement to a new string and keep going. Then, you only ever do one replacement for any given word. It raises questions about why bother having multiple replacements, but whatever. This is likely more efficient than looping over every word in the replacement list, and provably can't enter an infinite loop.

Sitten Spynne

What do you have in mind? I will implement your idea if you offer some help. Please help me in the way you can. I have been stack here for 6 months.

FunkyDexter

I found a code that can eliminate these kinds of problems. Have a look:

http://www.codeproject.com/Tips/4564...cation-Removal

FunkyDexter, Sitten Spynne, and kebo

Check the link here. How can I use that code to find duplicates, but before I delete them!

I want to copy these duplicates to a new file so that I will be able to know what to reuse or what to delete!

Quote:

---

Here is the part that does that job

---

That doesn't do that job. Here's the pseudo code for what that's actually doing:-

At this point CheckWord will be the index of the current word in the dictionary. e.ClickedItem.Text will be the value of the replacement word the user selected. so:-

Code:

---

Take each replacement word for the current word in the dictionary
  Set a variable called Auto1 to the replacement word
  Set the variable called Auto1 to the word the user actually selected
  Set a variable called kamau to the value of Auto1 (which will now be the value the user actually select)

---

So this will do a bunch of needless looping and the only external effect that it will have is to change the value of kamau to the word the user selected.
kamau is used elsewhere in the program here:-

Code:

---

RichTextBox1.SelectedText = GetWordWithOutBracketedText(kamau)

---

You seem to be passing that to the context menu as some kind of delegate although the code gets pretty mangled there (and I'm pretty sure would not compile) so I'm afraid I cannot infer your intention. Whatever, it's not going to do what you want because GetWordWithOutBracketedText doesn't return a value - so this would, at best, remove the selected text from the RichTextBox.

The first link is to an article on how to remove duplicates from a dictionary. I'm not sure of the relevance of that but it certainly has nothing to do with guarding against infinite loops. The second link is broken.

Sitten's brief algorithm which he gave in Post 6 is exactly what I would recommend but you'd have to completely ditch the code you've got already. From our exchanges in this and your previous thread I don't get the impression you're emotionally ready to do that.

The algorithm your code is currently trying to implement is valid but, I think, needlessly complicated, horribly inefficient with a large dictionary and unlikely to result in a decent user experience.
1. It's complicated enough that more than one experienced programmer has looked at your code and completely miss-interpreted what is going on. Even when we do start spotting the elements like the recursive loop we're still unable to decipher the nuances.
2. By including a recursion you do leave yourself open to an infinite loop unless you can guarantee an exit condition. I think you've managed to guarantee an error rather than a graceful exit but I'm not even 100% sure of that.
3. It's looping over the dictionary rather than the text box which is likely to be MUCH bigger so it's a very inefficient approach.
4. I don't think it will provide a good user experience because it will process the words in the order they appear in the dictionary, not in the order they appear in the text. That means it's going to be jumping around all over the place. Additionally, I don't see any way in which it's going to allow the user to change different instances of the same keyword to different replacement options.

After our exchanges in your previous thread and in this one I feel like I'm beating up on you which is something I really try to avoid as I think it's cruel and unnecessary. If that's the impression I'm giving I really do apologise. I don't want to discourage you in any way. The problem is that I think you're going about this all wrong but don't seem to be able to communicate that to you. I think you found some code on the web (which may or may have worked, even when it was posted) and you've adopted it without understanding it. Then you've hacked it around to try and make it fit your own problem without really trying to understand your own problem first. So you're trying to make some code you don't really understand solve a problem you don't understand - that's never going to work.

Your code to populate the dictionary in the load event is spot on. It's perfect and it will not result in any duplicates. Duplicates will not be an issue for you. Your code to actually use that dictionary makes some sense but very little and I'm pretty sure does not work as posted. I would encourage you to throw that bit away and go back to the drawing board.

That is very good. I see the light in your point. I'm only working on prototypes. I will consider your request, and begin things a new. The GetWordWithOutBracketedText(kamau) is working and is supposed to delete Educational comments like these:

counterproductive (It means negative or bad outcome)

Before counterproductive is posted, the Brackets and the comments are removed. Then you get counterproductive only as the answer. Anyway, I will see what I can do!

Good, it sounds like you're still in the fight and I haven't scared you off. That's a relief because I really don't want to do that and we got pretty close to home in your previous thread.

I would offer one other bit of advice at this stage. I think you might be trying to solve a big problem in one big bite. Don't! That's a bloody hard thing to do and defeats even the best programmers. Instead, solve it a little bit at a time:-

1. Work out how to iterate through the words in the text box one at a time and right that code. If you want to check it's working either step through the code using the debugging tools (this would be my recommendation) or just output each word in turn using a message box.
2. Work out how to check whether each word is in the dictionary's "keys" collection (ie. is it a word you want to replace). Again you can check you've got this right by stepping through the code or by only popping up a message box when a replaceable word is found.
3. Work out how to pop up a context menu containing the possible replacement words (I think you're code to do this is correct already but I haven't double checked). The check for this is obvious: the context menu will appear and will have the options you'd expect.
4. Work out how respond to the user selecting a replacement and replace the current word in the text box. The check for this is simply that it will replace the word as you expected it to.

If you try to do this in small steps you've got a very good chance of getting there. If you try to do it in one big lump it will defeat you (it would defeat any of us).



Edit>

Quote:

---

The GetWordWithOutBracketedText(kamau) is working and is supposed to delete Educational comments like these

---

I take back what I said about that not returning a value. It does return a value and does exactly what you're asking it to do. I'm not sure how I missed that on my last pass. I think I was still in C# mode and was looking for a return type on the beginning rather than the end of the declaration. Sorry.:blush: