Using find/replace and regex to replace keywords with URLs in a string

Because some of the phrases you want to link contain other phrases you want to link, and the links themselves will contain thses phrases too, you have to do it in two phases, if you want to avoid tricky regular expressions:

Phase 1: Replace each phrases with a unique ID for the phrase that will not match anything else:

• You will need to replace longer phrases before shorter phases to make sure you don't replace only part of a phrase (e.g. "London" in "London football events").
• You can store the phrases and URLs to be linked in a SortedDictionary, and provide an IComparer<string> that sorts strings by length then alphabetically. Note it is important that strings the same length still compare as different, or you can't store them both in the dictionary.
• As you replace each phrase you should generate the link that will replace it, and build a dictionary mapping IDs to links.
• If you use string.Replace to replace the phrases you will need to treat phrases that differ only by case as different phrases, i.e. "party sites in London" is different from "Party sites in London" and each will need to have a separate ID.

Phase 2: Replace all the placeholder IDs with the generated links.

Here's a class to do that:

class TextLinker : IComparer<string>
{
    private SortedDictionary<string, string> phrasesToUrls;

    public TextLinker()
    {
        // Pass self as IComparer to sort dictionary using Compare method.
        phrasesToUrls = new SortedDictionary<string, string>(this);
    }

    public void AddLink(string phrase, string URL)
    {
        phrasesToUrls.Add(phrase, URL);
    }

    public string Link(string text)
    {
        // phase 1: replace phrases to be linked with unique placeholders
        Dictionary<string, string> placeholdersToLinks =
            new Dictionary<string, string>();
        foreach (KeyValuePair<string, string> pair in phrasesToUrls)
        {
            // Replace phrases with placeholders.
            string placeholder = Guid.NewGuid().ToString();
            text = text.Replace(pair.Key, placeholder);
            // Create dictionary of links by placeholder
            string link = string.Format(
                "<a href=\"{0}\">{1}</a>",
                pair.Value,
                pair.Key);
            placeholdersToLinks.Add(placeholder, link);
        }
        // Phase 2: replace unique placeholders with links.
        foreach (KeyValuePair<string, string> pair in placeholdersToLinks)
        {
            text = text.Replace(pair.Key, pair.Value);
        }
        return text;
    }

    public int Compare(string x, string y)
    {
        if (x.Length > y.Length) return -1;
        if (x.Length < y.Length) return +1;
        // Equal length strings still need to be differentiated, otherwise
        // they will be treated as the same key by the  dictionary.
        return x.CompareTo(y);
    }
}

And here's an example of its use:

string input = "London is a great city and have football events " +
    "in London but party sites in London are also good. London " +
    "football events are great along with London party sites. " +
    "Enjoy London!";

TextLinker linker = new TextLinker();
linker.AddLink(
    "Football events in London",
    "http://www.mysite/footbal-events/london");
linker.AddLink(
    "football events in London",
    "http://www.mysite/footbal-events/london");
linker.AddLink(
    "London football events",
    "http://www.mysite/footbal-events/london");
linker.AddLink(
    "London",
    "http://www.mysite/london-events/london");
linker.AddLink(
    "Party sites in London",
    "http://www.mysite/party-sites/london");
linker.AddLink(
    "party sites in London",
    "http://www.mysite/party-sites/london");
linker.AddLink(
    "London party sites",
    "http://www.mysite/party-sites/london");

string output = linker.Link(input);

You could also overload the AddLink method to automatically generate phrases with alternative capitalization.

If London's getting replaced first, then your other regex strings no longer exist in the text.

Football events in London

is now

Football events in London

To elaborate on the other answers, you must put the longest and more complex string replacements first. eg.

Football events in London

London

If you do London as in your example, and replace it with Kent, any instance of "Football events in London" will become "Football events in Kent" and will not satisfy the Regular Expression.

PS: You might want to consider making this an extension method on string if you use it often.

What if you do the replacement recursively? i.e., every time a match is found, you replace it with the text in the dictionary and repeat the process but only for the parts of the text that haven't been matched.

As others have stated:

1. If you replace "London" before "Football events London", your search for "Football events London" won't match "Football events <a href="http://etc..>London<a>"
2. If you replace "Football events London" before "London", you will replace London inside the existing link for Football events London, which will give you a link within a link...
3. Dictionary is not ordered, so in either case you can't guarantee that you'll get the order you want if you are just foreaching through.
4. If your search texts are ALSO contained inside your urls, your code will also find those and replace them - this is especially the case as you made your regex non case-sensitive.
5. Including a leading space in the text of your a tags? That's a sign that you're doing something wrong somewhere else, and your compensating for it with a 'hack'.

Moral of story: find and replace (even with Regex) isn't going to cut it, I fear.

There are probably cleverer ways of doing this, but off the top of my head, here's something to look into, into pseudocode:

while(!input.EOS)
   for(longest to shortest key)
      if(input.indexOf(key) = 0)
          output += input.replace(key, url)
          input = remained of input
          matched = true
   if !matched then move first word from input to output

You'll have to fiddle with it a bit, especially because of whitespace issues (how/where will you match spaces and non-word characters?) Here is another tip to get you started: ^\s*(.+?)\s*\b

One thing you can do is the following:

Concatenate the keys (largest to smallest) into a single regular expression as such (assuming here that dictionary is an IDictionary<string, string>):

var pattern = string.Join(
    "|",
    dictionary.Keys.OrderByDescending(k => k.Length).Select(Regex.Escape).ToArray()
);
var regex = new Regex("(" + pattern + ")", RegexOptions.ExplicitCapture);

Note the use of Regex.Escape in the transformation function: we don't want special regex characters in the key to bugger things up.

A quick test has shown that .NET's regex engine will attempt matches in the order they appear within the pattern. This means that, when ordered correctly, the longer key will be attempted first and then the regex will move on, looking for new matches.

You can then loop through the matches and build a new string from the old as you go, instead of scanning the input string multiple times. These two techniques combined will eliminate both problems: premature and duplicate matches.

string input = "..."; // This is your input string.
int last = 0;
var output = new StringBuilder(input.Length);

foreach (Match match in regex.Matches(input)) {
    output.Append(input.Substring(last, match.Index - last); // Appends text between matches.
    output.AppendFormat(
        "<a href=\"{1}\">{0}</a>",
        match.Value,
        dictionary[match.Value]
    );
    last = match.Index + match.Length; // Moves the index to the end of this match.
}

Error checking not included. Also, the regular expression itself would probably benefit from \b anchors in the form of \b(...)\b. This is untested though, and I am off to bed.