On MMO-Champion, we often paste World of Warcraft patch notes taken from Blizzard. The main problem is that it's plain text. We want to be able to add links to all the spells, quests, zones ... This way people can mouseover and see the description. It helps figuring out what changed.

We create a Trie that contains item/spell/... names as key and url as value. For each letter of the text, we search the longest string in the trie that matches this part of the text. If found, we link it and move right after the end of the name, else we advance by one character.

Specialized Rules

The algorithm above works well but there are many little problems that arise. In order to solve them, we apply several specialized rules.

  • There are names that have more than one link. We proritize the source (Ability > Item > Quest > ...) and sort them by descending id.
  • All the interesting names start by a capital letter. This removes a lot of noise but keeps the first word of sentences.
  • Stamina, Gladiator, Buff, Stat. There are many common words that are spells, we have a blacklist to remove them.
  • [Heal]ing. If the name found ends in the middle of a word, we discard it.
  • [Cinderweb Spiderling]s. But there's an exception, if there is only an s after.
  • [Fireball] Barrage. If the next word is capitalized, it means the name is wrong.
  • [Sanctuary] of Malorne. We also discard if the next word is of.

Example

Druid

  • Druids now gain 1 attack power per point of Strength, down from 2. They continue to gain 2 attack power per point of Agility while in Cat Form or Bear Form. In addition, Cat Form's scaling rate from gear upgrades was slower than other classes, which was causing them to fall behind in damage with higher item levels. To counter the Strength change and improve scaling, the following changes have been made. All numbers cited are for level-85 druids.
  • Ferocious Bite damage has been increased by 15%. In addition, its base cost has been reduced to 25 energy and it can use up to 25 energy, for up to a 100% damage increase.
  • Mangle (Cat) damage at level 80 and above has been increased to 540% weapon damage, up from 460%, and bonus damage has been lowered to 302.
  • Rake initial damage on hit now deals the same damage as each periodic tick (and is treated the same for all combat calculations). Periodic damage now gains 14.7% of attack power per tick, up from 12.6%, and base damage per tick has been lowered from 557 to 56. There is a known issue with Rake's tooltip being incorrect from this change will be corrected in a future patch.
  • Ravage damage at level 80 and above has been increased to 950% weapon damage, up from 850%, and bonus damage has been lowered to 532.
  • Savage Roar now grants 80% increased damage to melee auto attacks, up from 50%. The Glyph of Savage Roar remains an unchanged bonus of 5% to that total.
  • Shred damage at level 80 and above has been increased to 540% weapon damage, up from 450%, and bonus damage has been lowered to 302.
  • Entangling Roots and the equivalent spell triggered by Nature's Grasp no longer deal damage.
  • Innervate now grants an ally target 5% of his or her maximum mana over 10 seconds, but still grants 20% of the druid's maximum mana over 10 seconds when self-cast.
  • Omen of Clarity clearcasting buff from now lasts 15 seconds, up from 8 seconds.
  • Starfire damage has been increased by approximately 23%.
  • Swipe (Cat) now deals 600% weapon damage at level 80 or higher, down from 670%.
  • Wrath damage has been increased by approximately 23%.

Rest of the example ...

Conclusion

It takes around a minute to generate the trie, which needs to be done once per big patch. Then it takes less than a second to process a full patch note, automatically adding around 700 links.

The script does not generate a perfect output and needs to be reviewed by a human. However, it takes an order of magnitude less time to improve the generated result than doing it from scratch.