{"id":120,"date":"2020-02-02T00:10:18","date_gmt":"2020-02-02T00:10:18","guid":{"rendered":"http:\/\/blog.gunlerveisler.gen.tr\/?p=120"},"modified":"2020-02-02T00:10:18","modified_gmt":"2020-02-02T00:10:18","slug":"pipe-and-filter-architecture-and-an-elegant-algorithm","status":"publish","type":"post","link":"https:\/\/aliyargunes.com.tr\/blog\/pipe-and-filter-architecture-and-an-elegant-algorithm\/","title":{"rendered":"Pipe-and-Filter Architecture and An Elegant Algorithm"},"content":{"rendered":"\n

The Problem: Given a dictionary of words in English, find all the anagrams in the dictionary. That is, find all the words that are permutations of each other. For example, pots, stop, and spot are anagrams of each other.<\/p>Bentley, J. Programming Pearls, Second Edition. (Boston, MA: Addison-Wesley, 2000.)<\/cite><\/blockquote>\n\n\n

First of all, all the anagrams have the same letters and the same number of letters in each word. That gives us the clue to the method you\u2019ll use to find the anagrams. If you sort each word by individual letters, you\u2019ll end up with a string of characters that has all the letters in the word in alphabetical order. We call this creating a sign for the word. If you then sort the resulting list, all the anagrams will end up together in the sorted list because their sorted letters will be identical. If you then keep track of which words you sorted, you can then simplify the list and create a new list with, say, each set of anagrams on the same line of the output file. This is exactly how Bentley does it. But how does this relate to a pipe-and-filter architecture, you ask? Good question. Let\u2019s break down the solution again.<\/p>\n\n\n

  1. Create a sign for each word in the list by sorting the letters in each word; keep the
    sign and the word together.<\/li>
  2. Sort the resulting list by the signs; all the anagrams should now be together.<\/li>
  3. Squash the list by putting each set of anagrams on the same line, removing the
    signs as you do. <\/li><\/ol>\n\n\n

    sign <dictionary.txt| sort | squash> anagrams.txt <\/p>\n\n\n

    sign is the filter we use to do step 1, with input file dictionary.txt. sign outputs a list of signs and their associated words, which is piped to the sort utility. Sort then sorts the list by the first field on each line, which happens to be the sign of each word. It then outputs the sorted list to the next pipe. Squash takes the sorted list from the incoming pipe and compresses it by putting all the words with the same sign on the same line, eliminating the signs as it does so. This final list is sent via one last pipe to the output file anagrams.txt.<\/p>\n\n\n

    \"\"<\/figure><\/div>\n\n
    <\/a>
    Anagram Program (The GNU Awk User\u2019s Guide)<\/div>
    Column 2, Problem C, of Jon Bentley\u2019s Programming Pearls, Second Edition, presents an elegant algorithm. The idea is to give words that are anagrams a common signature, sort all the words together by their signatures, and then print them. Dr. Bentley observes that taking the letters in each word and sorting them produces those common signatures.<\/div><\/div><\/div>\n\n

    <\/p>\n","protected":false},"excerpt":{"rendered":"

    The Problem: Given a dictionary of words in English, find all the anagrams in the dictionary. That is, find all the words that are permutations of each other. For example, pots, stop, and spot are anagrams of each other. Bentley, … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9,11,12,13],"tags":[15,18,47,48],"class_list":["post-120","post","type-post","status-publish","format-standard","hentry","category-algorithm-analysis","category-general-concepts","category-links","category-software-architecture","tag-anagram","tag-bentley","tag-pipe-and-filter-architecture","tag-programming-pearls"],"_links":{"self":[{"href":"https:\/\/aliyargunes.com.tr\/blog\/wp-json\/wp\/v2\/posts\/120"}],"collection":[{"href":"https:\/\/aliyargunes.com.tr\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/aliyargunes.com.tr\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/aliyargunes.com.tr\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/aliyargunes.com.tr\/blog\/wp-json\/wp\/v2\/comments?post=120"}],"version-history":[{"count":1,"href":"https:\/\/aliyargunes.com.tr\/blog\/wp-json\/wp\/v2\/posts\/120\/revisions"}],"predecessor-version":[{"id":810,"href":"https:\/\/aliyargunes.com.tr\/blog\/wp-json\/wp\/v2\/posts\/120\/revisions\/810"}],"wp:attachment":[{"href":"https:\/\/aliyargunes.com.tr\/blog\/wp-json\/wp\/v2\/media?parent=120"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/aliyargunes.com.tr\/blog\/wp-json\/wp\/v2\/categories?post=120"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/aliyargunes.com.tr\/blog\/wp-json\/wp\/v2\/tags?post=120"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}