（转）lookup table（查表法）

lookup table（查表法）

 

转自：

 

在讲lookup table技术之前，先讲一下“回溯引用”
        回溯引用对于大家来说并不陌生，会经常用于 s/REGEXP/REPLACEMENT/ 中REPLACEMENT部分
        但回溯引用并不是只能用于REPLACEMENT部分，在REGEXP中也是可以使用的。
       
        例1：找出100以内，个位与十位相同的2位数

1.  ly5066113@ubuntu:~$ seq 100 | sed -n '/^\(.\)\1$/p'

2.  11

3.  22

4.  33

5.  44

6.  55

7.  66

8.  77

9.  88

10. 99

我们可以看到，这个问题利用回溯引用很容易解决。
        \1表示前面\(.\)中内容，换种说法就是\1与前面\(.\)是相同的，那么就是个位与十位相同了


        在理解了REGEXP中的回溯引用之后，我们来看看lookup table技术
        lookup table就是回溯引用的方式进行前后定位，然后取出我们需要内容

        例2： AIX下怎么用DATE取上月的月份
       
        UNIX下一般都没有GNU date，即便有GNU date，在某些时间点(如3月31号)上进行取上月操作(-1 month)的时候也有问题

1.  ly5066113@ubuntu:~$ date +%m

2.  08

3.  ly5066113@ubuntu:~$ date +%m | sed 's/$/b12a01a02a03a04a05a06a07a08a09a10a11a12/;s/^\(..\)b.*\(..\)a\1.*/\2/'

4.  07

我们来看看这段代码是如何工作的：
        1、构造一个列表，字母a左边的2位数字是右边2位数字的上一个月
        2、利用lookup table取出上一个月

        pattern space初始为：
        08
        第一个s命令处理后pattern space变为：
        08b12a01a02a03a04a05a06a07a08a09a10a11a12
        下面我们重点来看看第二个s命令是怎么工作的：
        s/^\(..\)b.*\(..\)a\1.*/\2/
        将pattern space里面的内容按照上面的正则表达式进行分解
        ^\(..\)              08
        b.*                  b12a01a02a03a04a05a06a
        \(..\)               07
        a\1                  a08
        .*                   a09a10a11a12
        整个过程就是通过第一个括号里面的内容 08 ，定位到后面的 a08 ，从而取出它前面的2位数字 07 ，也就是第二个括号里的内容 \2
        这种方法就称之为 lookup table


        例3：文本处理
       

1.  ly5066113@ubuntu:~$ cat urfile

2.  172.27.38.0&1=99&2=100

3.  192.168.9.2&1=100&3=111

4.  202.96.64.68&1=99&2=1&3=111

5.  202.96.69.38&1=99&3=111&4=110

6.  202.77.88.99&1=99&2=111&3=66&4=100&5=44

7.  ly5066113@ubuntu:~$ sed -r 's/&/\n1\n2\n3\n4\n5&/;:a;s/\n(.)(.*)&\1=([^&]+)/\t\3\2/;ta;s/\n./\t0/g' urfile

8.  172.27.38.0     99      100     0       0       0

9.  192.168.9.2     100     0       111     0       0

10. 202.96.64.68    99      1       111     0       0

11. 202.96.69.38    99      0       111     110     0

12. 202.77.88.99    99      111     66      100     44

整体思路，用原贴中dream3401的描述：
        1、产生1,2,3,4,5的"坐标"
        2、对每天"有坐标的赋值"中的值代入坐标
        3、对没有"赋值的坐标"代入0

        我们以第一行数据为例，看看这段代码是怎么工作的：
        pattern space初始为：
        172.27.38.0&1=99&2=100
        s/&/\n1\n2\n3\n4\n5&/后：
        172.27.38.0\n1\n2\n3\n4\n5&1=99&2=100
        s/\n(.)(.*)&\1=([^&]+)/\t\3\2/后：
        172.27.38.0     99\n2\n3\n4\n5&2=100
        s命令执行成功，t命令执行，跳转到标签a处，再次执行s/\n(.)(.*)&\1=([^&]+)/\t\3\2/：
        172.27.38.0     99      100\n3\n4\n5
        s命令执行成功，t命令执行，跳转到标签a处，再次执行s/\n(.)(.*)&\1=([^&]+)/\t\3\2/，s命令执行失败，无替换
        t命令不执行，执行s/\n./\t0/g：
        172.27.38.0     99      100     0       0       0

        对于以上步骤，第一个s命令和最后一个s命令都不难理解，关键是中间的这句：
        s/\n(.)(.*)&\1=([^&]+)/\t\3\2/
        那我们以第一次的执行为例，将pattern space里面的内容按照上面的正则表达式进行分解
        \n(.)                \n1
        (.*)                 \n2\n3\n4\n5
        &\1=                 &1=
        ([^&]+)              99
        利用第一个括号的数字1，定位到后面&1=中的数字1，从而取出=号后面的数字99
        172.27.38.0                \n1\n2\n3\n4\n5&1=99                &2=100
        172.27.38.0     99\n2\n3\n4\n5                                &2=100
        此正则表达式在工作的过程中，开头的 172.27.38.0 和结尾的 &2=100 都是没有处理的，处理的只是中间的一部分


        例3和例2虽然都是用的lookup table技术，但思路梢有不同。
        例2是构造一个列表，然后从列表中lookup出想要的值
        例1也是构造一个列表，但是将外面的值填充到列表中
        无论是那种方式，lookup table技术的基本做法都是先构造一个列表，然后用回溯引用定位，从而得到我们需要的值