Editing Aho–Corasick algorithm (section)

==History==

Like many inventions at Bell Labs at the time, the Aho–Corasick algorithm was created serendipitously with a conversation between the two after a seminar by Aho. Corasick was an information scientist who got her PhD a year earlier at Lehigh University. There, she did her dissertation on securing propretiary data within open systems, through the lens of both the commercial, legal, and government structures and the technical tools that were emerging at the time.<ref>{{cite thesis |last=Corasick |first=Margaret J. |title=A Study of the Means of Protection and the Legal Framework in Which Such Protection Is Undertaken |year=1974 | institution =Lehigh University |url=https://preserve.lehigh.edu/_flysystem/fedora/2024-12/7510364.pdf}}</ref> In a similar realm, at Bell Labs, she was building a tool for researchers to learn about current work being done under government contractors by searching government-provided tapes of publications.

For this, she wrote a primitive keyword-by-keyword search program to find chosen keywords within the tapes. Such an algorithm scaled poorly with many keywords, and one of the bibliographers using her algorithm hit the $600 usage limit on the Bell Labs machines before their lengthy search even finished.

She ended up attending a seminar on algorithm design by Aho, and afterwards they got to speaking about her work and this problem. Aho suggested improving the efficiency of the program using the approach of the now Aho–Corasick algorithm, and Corasick designed a new program based on those insights. This lowered the running cost of that bibliographer's search from over $600 to just $25, and Aho–Corasick was born.<ref>{{cite video |last=Aho |first=Alfred |title=Alfred V. Aho Oral History |url=https://www.youtube.com/watch?v=ir9Mwl9zhIM&t=3598s |publisher=YouTube |date=2023-08-12 |access-date=2025-04-18}}</ref>