用sed實現wc -w的功能_ZenDei技術網路在線

sed是所謂的流編輯器，我們經常用它來做一些文本替換的事情，這是sed最擅長的事情，如sed 's/Bob/Tom/g'就是把文章中所有的Bob改成Tom。 sed是圖靈完備的，作為sed的粉絲，喜歡用sed做各種sed不擅長的事情，這裡實現一下wc -w的功能，也就是統計文章單詞數量。我習慣喜歡 ...

　　版權申明：本文為博主窗戶(Colin Cai)原創，歡迎轉帖。如要轉貼，必須註明原文網址

　　http://www.cnblogs.com/Colin-Cai/p/7663831.html 

　　作者：窗戶

　　QQ：6679072

　　E-mail：[email protected]

　　sed是所謂的流編輯器，我們經常用它來做一些文本替換的事情，這是sed最擅長的事情，如sed 's/Bob/Tom/g'就是把文章中所有的Bob改成Tom。

　　sed是圖靈完備的，作為sed的粉絲，喜歡用sed做各種sed不擅長的事情，這裡實現一下wc -w的功能，也就是統計文章單詞數量。

　　我習慣喜歡加上n和r，n表示每行結束時不會自動列印，r表示正則表達式的擴展方式，我實在很討厭寫那麼多\，所以sed基本上我是一定加這兩個東西的。

　　先從sed擅長的開始，先用s命令做替換，把每個單詞都替換為單個1。這一步其實很簡單，s/[^ \t\r]+/1/g即可，也就是把不是空格的連續匹配替換為1，g是表示對一行中所有滿足這樣的模式都替換為1，再考慮到正則表達式的貪婪，其實我們的[^ \t\r]+實際上就是指完整的一個單詞，熟悉regex替換的應該不難理解。

　　然後為了整齊，替換為1之後，再把空格都去掉，其實也就是把不是1的去掉，那麼緊接著一條s/[^1]+//g即可，然後再用p列印一下。

　　一口吃不成胖子，先從簡單的來，我們可以看一下效果。在此之前先找篇文章，就節選一下google的pixel buds新聞吧。

linux-p94b:/tmp/testhere # cat 1.txt
American company Google recently announced the release of its Google Pixel 2 phone and other products that work together with the phone.
One of the new products is a pair of wireless earphones Google calls Pixel Buds.
The earphones are seen as the company's answer to competitor Apple's popular AirPod headphones.
At a launch event on October 4, Google said its Pixel Buds were built to provide high-quality sound and hands-free use. All of their operations can be controlled by simply touching the right earphone.
Once the headphones are paired with a Pixel phone, its many features can be used through the Pixel Buds.
One example is Google Assistant, the company's artificial intelligence, or AI, service. Users can now talk directly to Pixel Buds to ask Google Assistant questions, get information or other help. This can all be done without touching the telephone.
The Pixel Buds also can work with Google Translate, the service that provides words and expressions in over 100 languages.
Google product manager Juston Payne demonstrated this feature during the launch event. He was able to talk with someone whose native language is Swedish.
When the person spoke Swedish into the Pixel Buds, the phone's speakers provided the translation in English. The English speaker's response was then translated in real time into Swedish and heard through the Pixel Buds.
linux-p94b:/tmp/testhere # cat wc-w.sed
#!/usr/bin/sed -nrf
s/[^ \t\r]+/1/g
s/[^1]+//g
p
linux-p94b:/tmp/testhere # ./wc-w.sed <1.txt
1111111111111111111111
111111111111111
11111111111111
1111111111111111111111111111111111
1111111111111111111
111111111111111111111111111111111111111
11111111111111111111
111111111111111111111111
11111111111111111111111111111111111

　　對一下，確實沒有錯，只是出來了一堆1，而且還是分行的，那麼第二步，把這個分行給去掉。當然，加個管道，tr -d '\n'就去掉了，不過我們要的是單個sed解決，那麼需要再動一點點腦筋。

　　我們可以在上面的基礎上稍微改動改動，把這些1先緩存進保持空間(hold space)，最後再從保持空間中取出，然後用s/\n//g去掉所有的回車符，再列印。

linux-p94b:/tmp/testhere # cat wc-w.sed
#!/usr/bin/sed -nrf
s/[^ \t\r]+/1/g
s/[^1]+//g
H
$ {
        g
        s/\n//g
        p
}
linux-p94b:/tmp/testhere # ./wc-w.sed <1.txt
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

　　H命令就是放在保持空間的最後，$是判定輸入結束，g是用保持空間的內容替換模式空間。

　　上面列印出了222個1，離結果222已經很近了。

　　最後就是如何整合成222了，這裡的確是需要一點點技巧了。我們建立以下計數方法：

　　1..1;1..1;1..1...

每一堆1的個數假設為n_k,n_k-1,...,n₀

　　允許數量為0的堆

　　每一堆1之間用分號隔開，如果看到有多個分號在一起，那麼中間實際上有數量為0的堆

　　整個計數表示的是n_k*10^k+n_k-1*10^k-1+...+n₀

　　很明顯，我們十進位表示方法和整個很類似，只是，十進位表示里，每一堆都小於10而已。

　　於是我們可以創立一個演算法，也就是，當我們發現一堆里有10個1，那麼我們就可以往高位進1。

　　很容易證明這個演算法可以結束。

　　假設{n_k,n_k-1,...,n₀}有限序列是非負整數num的一個表示，序列里的每一個數字是一個非負整數，最高位n_k大於0，除非num等於0。

　　顯然，一個具體整數的表示方法是有限的，實際上，這個k不可能大於num對10取對數，序列中的每一項不可能大於num。

　　序列可以比較大小，

　　{m_j,m_j-1,...,m₀}有限序列是num的另外一個表示，那麼

　　{n_k,n_k-1,...,n₀} 〉{m_j,m_j-1,...,m₀} 當且僅當 k > j 或者 k = j且n_k=m_k...n_k-p=m_k-p,n_k-p-1>m_k-p-1

　　以上比較大小的方法可以把一個非負整數的所有表示串成一個全序集。

　　之前的演算法中，每當升位，其表示都會變的比之前大。因為所有的表示為有限個，而最大的表示則是十進位的表示方法，從而可以知道演算法是可以結束得到十進位表示的。

　　那麼我們根據這個，不停的找10個0，每當找到，就進位，最後再把每堆挨個替換為9,8,7,6,5,4,3,2,0，再去掉分號，就完成了。有點費腦子吧，我實現一下如下:

linux-p94b:/tmp/testhere # cat wc-w.sed
#!/usr/bin/sed -nrf
s/[^ \t\r]+/1/g
s/[^1]+//g
H
$ {
        g
        s/\n//g
        :a
        s/;1111111111/1;/
        s/^1111111111/1;/
        ta
        s/111111111/9/g
        s/11111111/8/g
        s/1111111/7/g
        s/111111/6/g
        s/11111/5/g
        s/1111/4/g
        s/111/3/g
        s/11/2/g
        :b
        s/;;/;0;/g
        tb
        s/;$/;0/
        s/;//g
        /^$/s/^/0/
        p
}
linux-p94b:/tmp/testhere # ./wc-w.sed <1.txt
222