王維維，李仁旺，趙亞平，王海周，宋圣濤

(1.浙江理工大學機械與自動控制學院，杭州 310018；2.南京師范大學生命科學學院，南京 210046)

?

Linux文件搜索命令解析以及l(fā)ocate命令查詢優(yōu)化

王維維1，李仁旺1，趙亞平2，王海周1，宋圣濤1

(1.浙江理工大學機械與自動控制學院，杭州 310018；2.南京師范大學生命科學學院，南京 210046)

隨著linux系統(tǒng)逐漸被廣泛使用，系統(tǒng)使用者一般使用命令行的方式操作系統(tǒng)包括文件查找，特別是將linux系統(tǒng)作為服務器時，在數(shù)量眾多的文件中找到需要的文件需要消耗很多時間，為了更快找到所需要的文件，針對現(xiàn)有的兩種linux文件搜索命令的實現(xiàn)原理以及實現(xiàn)過程進行剖析，以及對著名的Boyer- Moore串匹配算法進行分析后，使用改進的BM算法對其中一種搜索命令即locate命令中字符串匹配算法進行優(yōu)化，對改進算法的復雜度進行分析發(fā)現(xiàn)，在文件名的字符串匹配過程中與原來KMP算法相比較具有更高的效率，查找的速度更快。

linux文件搜索；find命令；locate命令；BM算法；updatedb命令

0　引　言

linux是一個開源軟件，用戶可以自由地獲取程序和源代碼，能夠自由地修改和使用它們，隨著網(wǎng)絡的發(fā)展，linux愛好者以及眾多技術(shù)人員已對其研究和完善。linux系統(tǒng)有著廣泛的應用前景，特別是在嵌入式領(lǐng)域，移動通信設(shè)施、便攜計算機、平板電腦、消費電子領(lǐng)域甚至軍事領(lǐng)域都或多或少的存在嵌入式系統(tǒng)的影子[1]。在linux系統(tǒng)越來越普遍的情況下，如何使用命令行來查詢系統(tǒng)中用戶需要的文件以及采用哪種方式可以提高效率是用戶特別是程序開發(fā)人員關(guān)心的問題。目前在linux系統(tǒng)中主要的查詢命令有find和locate兩種。find命令提供了很多的查找條件，包括文件名稱、時間、文件類型、用戶名稱、文件大小等，功能比較強大，但是查詢需要時間比較多，平時個人電腦中使用這個命令感覺不到，如果在文件很多或者服務器中搜索需要很長的時間。locate命令查詢的文件名存儲在一個數(shù)據(jù)庫文件中，但是數(shù)據(jù)庫中只有目錄時間和文件名稱。如果要查詢某一文件需要先運行updatedb命令對數(shù)據(jù)庫進行更新，否則無法檢測到新增的文件，但是linux系統(tǒng)會定期執(zhí)行這個命令。locate命令搜索時間快，局限性是只能根據(jù)文件的名稱進行搜索。locate命令就是對用戶輸入的字符串和文件的路徑名采用KMP算法的一個匹配的過程。本文在linux查找命令詳細分析的基礎(chǔ)上，用改進的BM算法對原來的KMP字符串模式匹配算法進行優(yōu)化。

用戶輸入的字符串稱為模式串，系統(tǒng)中所有文件的絕對路徑稱為文本串。模式匹配的問題可描述為：

文本串：T = T0T1…Tn-1；

模式串：P = P0P1…Pm-1.

其中：n>m。要求在T文本串中找到等于模式串P的子串，如果T中存在P的子串則匹配成功，否則匹配失敗，相當于在眾多路徑中選擇出含有用戶輸入的字符串的路徑。

1　find命令

find命令是通過find(char *arg)函數(shù)讀取并且選擇出符合用戶要求的文件名稱。這個函數(shù)用FTS數(shù)據(jù)結(jié)構(gòu)來記錄一個文件層次的句柄，它由函數(shù)fts_open()返回，代表文件層次本身也相當于一個目錄，另一個是FTSENT代表文件層次里面的文件，fts_read()函數(shù)都會返回每個文件的一個FTSENT結(jié)構(gòu)。FTSENT數(shù)據(jù)結(jié)構(gòu)里面含有該文件的訪問路徑、根路徑、文件名以及索引節(jié)點信息。consider_visiting()函數(shù)會根據(jù)該結(jié)構(gòu)里面的內(nèi)容判斷該路徑是否是用戶需要查找的結(jié)果，find函數(shù)的部分代碼如下：

find(char *arg){

…

FTS *p;

FTSENT *ent;

…

p = fts_open(arglist, ftsoptions, NULL);

…

while ( (ent=fts_read(p)) != NULL )

{

consider_visiting(p, ent);

}

}

該函數(shù)參數(shù)是用戶輸入的字符串，包括查詢條件以及要查詢的文件名稱等，首先會用fts_open()返回用戶輸入的目錄參數(shù)的一個句柄，也就是文件層次，然后遍歷文件層次里面的文件判斷是否符合條件。對于文件層次、文件名稱、索引節(jié)點之間的關(guān)系則由文件系統(tǒng)組織結(jié)構(gòu)決定。

linux文件系統(tǒng)都相應的被劃分至少4個部分，其中引導塊是介質(zhì)上的第一個塊，索引節(jié)點則取決于磁盤大小等參數(shù)，這些參數(shù)都存儲在超級塊當中[2]。linux文件系統(tǒng)由引導快和分區(qū)或者記錄塊組組成，分區(qū)的數(shù)量取決于設(shè)備的容量和分區(qū)大小，如圖1所示。

索引節(jié)點(i節(jié)點) 用于存儲文件的元數(shù)據(jù)的一個數(shù)據(jù)結(jié)構(gòu)。文件的元數(shù)據(jù)，也就是文件的相關(guān)信息，和文件本身是兩個不同的概念。它包含文件的大小，創(chuàng)建時間，修改時間，擁有者磁盤位置等和文件相關(guān)的信息。當訪問文件的內(nèi)容必須要通過i節(jié)點。

圖1　linux系統(tǒng)文件格式

但是文件名不包含其中，當知道一個文件名稱時候想知道這個文件相關(guān)的信息，這就是目錄樹的作用，目錄樹中包含目錄名、索引節(jié)點以及數(shù)據(jù)部分，數(shù)據(jù)部分也就是各個目錄項[2]。該目錄相對于電腦上面的文件夾，目錄項相當于文件夾里面的文件或者子目錄以及其他一些信息。從專業(yè)角度說，目錄是對文件管理的有效信息集合，也就是說看到的文件夾也就是目錄的形式化表示[3]，目錄樹的結(jié)構(gòu)圖如圖2所示。所以該函數(shù)用FST結(jié)構(gòu)獲取當前目錄的文件層次也就是該目錄，然后遍歷該文件層次獲取文件的FTSENT的數(shù)據(jù)結(jié)構(gòu)，如果用戶值用find命令在根目錄下查找文件名為find.c的文件：find / -name find.c，則不需要使用索引節(jié)點，只需要判斷用戶名是否符合用戶要求。如果需要根據(jù)文件的權(quán)限、所有者、類型等去查找則需要去使用索引節(jié)。例如find / -perm 777。find命令查詢的范圍比較廣，能滿足用戶的各種查詢需求，但是每次都需要遍歷文件層次以及文件和索引節(jié)點信息，消耗的時間比較多。

圖2　目錄樹結(jié)構(gòu)

2　updatedb命令

updatedb用來建立或者更新數(shù)據(jù)庫，該數(shù)據(jù)庫主要包含文件的名稱以及文件的修改時間。一般位于/var/lib/mlocate/mlocate.db目錄下，這個數(shù)據(jù)庫已經(jīng)存在它將讀取未改變的部分以及將發(fā)生改變的部分重新寫入其中。updatedb是由cron命令每天每隔一段時間更新數(shù)據(jù)庫。updatedb的實現(xiàn)原理是將文件名或者目錄名以及每個目錄的時間以一定的格式寫入mlocate.db數(shù)據(jù)庫。

它在執(zhí)行之前，需要讀取名稱/etc/updated.conf的文件檢索配置信息，這個配置信息會過濾一些不需要檢索的文件，提高檢索速度。updatedb.conf內(nèi)容如下：

PRUNE_BIND_MOUNTS=“yes”：是否掃描mount過來的文件系統(tǒng)的文件，yes:1, no:0。

PRUNENAMES=“.git .bzr .hg .svn”:表示對哪些后綴的文件不采取檢索, 也就是列在這里面的后綴。

PRUNEPATHS=“/tmp /var/spool/media”:表示不檢索的路徑, 即列出的路徑下的文件和子文件夾均跳過不進行檢索。

mlocate.db是有一定格式的數(shù)據(jù)庫文件,它是由含有16字節(jié)的頭部，配置文件信息，路徑為“/”的根目錄和數(shù)據(jù)區(qū)組成，該數(shù)據(jù)區(qū)記錄在一定時間某個路徑下面所含有的文件名稱和類型，它含有一個結(jié)束，符標志該數(shù)據(jù)區(qū)結(jié)束，其內(nèi)容結(jié)構(gòu)如圖3所示。

圖3　mlocate.db數(shù)據(jù)庫內(nèi)容結(jié)構(gòu)

這些功能都由scan函數(shù)實現(xiàn)，主要實現(xiàn)過程如下：

static int scan()

{

…//根據(jù)文件配置信息檢查文件名是否符合目

錄要求

if(old_dir.path…) //路徑和時間符合要求

{

copy_old_dir(&dir)//從舊的數(shù)據(jù)庫中讀

取信息

goto have_dir

}

scan_cwd(&dir) //時間不符合要求重新掃描

該目錄

have_dir：write_directory(&dir) //寫入數(shù)據(jù)

庫

if (have_subdir != false) { //含有與子文件

夾

scan_subdirs(&dir, &st) //繼續(xù)調(diào)用

scan遞歸掃描該目錄的子文件夾

}…

}

當數(shù)據(jù)庫未建立的時候，updatedb先寫入頭部信息，以及配置文件信息，然后主要是從根目錄掃描文件系統(tǒng)，獲取文件名字以及文件類型，并且根據(jù)文件的名稱排序。寫入數(shù)據(jù)庫的過程中先寫入該文件夾上次修改對應的時間(s，ms)，以及該文件夾的路徑，接下來按排好后的順序依次寫入文件類型(文件或者目錄)、文件名稱，最后寫入結(jié)束符。然后對已經(jīng)寫入數(shù)據(jù)庫的并且是文件目錄的，執(zhí)行遞歸操作，直到所有文件都已經(jīng)訪問并寫入數(shù)據(jù)庫。

當數(shù)據(jù)庫已經(jīng)建立之后，updatedb從原先數(shù)據(jù)庫讀取頭部，配置信息寫入一個新的數(shù)據(jù)庫，然后開始讀取數(shù)據(jù)區(qū)，它依照原有數(shù)據(jù)庫中依次讀取記錄，每當讀取一個數(shù)據(jù)區(qū)或者文件夾后，它用數(shù)據(jù)庫中時間與現(xiàn)在文件夾中最近一次更新的時間進行對比，如果時間沒有改變那么直接寫入新數(shù)據(jù)庫，否則重新掃描該目錄下的所有文件然后寫入，直到結(jié)束。

3　locate命令

locate命令能夠快速查找文件從mlocate .db數(shù)據(jù)庫中，當前新創(chuàng)建的文件最好需要先運行updatedb命令，否則最新的文件可能不在數(shù)據(jù)庫中。locate實現(xiàn)原理是按照一定的格式從mlocate .db讀取數(shù)據(jù)區(qū)的數(shù)據(jù)，這個格式與updatedb命令寫入的格式相同。然后對路徑加上文件名之后的字符串相當于正文與需要查找的字符串相當于模式串之間匹配，代碼中mbsstr函數(shù)用的匹配算法是KMP算法。

3.1KMP算法

KMP算法[4]的思想是利用已經(jīng)匹配的結(jié)果將模式串P向右移動一定的距離[5]。首先將模式串P和文本T左端對其進行比較，比較Pi和Tj時，若相等則繼續(xù)向右比較；若不等則正文中j位置不變，模式中i指向next[i]所致的位置，next[i]表示第i個字符與主串中相應的字符“失配”時，在模式中需重新和主串中的該字符進行比較的字符的位置。這個位置與模式本身有關(guān)與正文無關(guān)。

KMP算法的搜索階段在最壞的情況下的復雜度為O(m×n)，但是在一般情況下的時間復雜度為O(m+n)，其中next[i]的時間復雜度為O(m)[6]。

3.2BM算法

BM( Boyer-Moore) 算法[7]是一種效率較高的算法，在實際應用中采用較多，很多種文本編輯器的“查找”功能(Ctrl+F)采用Boyer-Moore算法[8]。BM算法提出了一個巧妙的方法，從字符串的尾部開始比較來解決匹配問題。它是最早的跳躍型算法，通過兩個啟發(fā)規(guī)則來確定掃描窗口的跳躍距離[9]。

首先，模式串與文本串頭部對齊，從尾部Pm-1開始比較。因為如果尾部字符不匹配，那么只要一次比較，就可以判斷文本串的前m個字符肯定不是要找的結(jié)果。當模式串和文本串從右邊開始Pi≠Tj開始不匹配時，該不匹配字符就被稱為“壞字符”。則對應的移動距離為壞字符出現(xiàn)的位置減去搜索詞中上一次出現(xiàn)的位置。如果壞字符不在字符中，則上次搜索的位置為-1。

已經(jīng)匹配了的字符串稱為“好后綴”，好后綴的位置以最后一個字符為準，如果好后綴在搜索詞中只出現(xiàn)一次，則它的上一次出現(xiàn)位置為 -1，如果好后綴有多個，則除了最長的那個好后綴，其他好后綴的上一次出現(xiàn)位置必須在頭部。每一次完成之后它會根據(jù)壞字符移動表和好后綴移動表來進行位置后移。假設(shè)i為壞字符，P[i+1,m-1]為好后綴。

對于壞字符: distanceChar = {i-k| (P[i]≠T[j]) &&(P[i]=P[k](k

對已好后綴則有distanceFix =

移位結(jié)果為：dist[i]=max(distanceChar, distanceFix)。

BM算法使用好后綴移動與壞字符移動計算得到的移動中的最大值來向后移動嘗試位置。KMP算法與BM算法在最壞的情況下均具有線性的搜索時間，但是在實際的應用中BM算法往往比KMP算法快上3～5倍，比較次數(shù)只有文本串長度的20%～30%[10]。

3.3改進的BM算法

3.3.1改進的BM算法的思想

對于BM算法都是根據(jù)好后綴和壞字符算法,都是從尾部開始比較，但是有一定的局限性。例如從字符串的末尾開始匹配且匹配了后面的字符串的時候發(fā)現(xiàn)首字符不匹配，則此次匹配是失敗的，除首字符之外的所有匹配都無用。所以一個字符串不僅尾部需要匹配而且還需要匹配字符串的開頭部分，具有好后綴的時候還應該具有一個好開頭，好開頭就是模式串的第一個字符。因此本文提出一種BM的改進算法。算法的思想是：將首字符P[0]與T[j]對齊，末尾字符P[m-1]和T[j+m]對齊。當末尾符為壞字符即P[m-1]≠T[j+m]時按照普通BM算法向右移動dist個字符的距離。當末尾字符相同且首字符不同，即P[0]≠T[j]，此時向右移動一位以減少字符串的回溯比較。當末尾字符和首字符都不相同時，則使用BM算法進行dist個字符位置移動。 對模式串P=“abcdc”和文本串T=“ebcdcabfbccdcabcdc”，改進的BM的算法的匹配過程如表1所示。

表1　改進的BM的算法的匹配過程

比較過程：第一趟比較首字符不匹配末尾字符匹配，此時向右移動一位。第二趟末尾字符出現(xiàn)了不匹配的按照BM算法向右移動四位。第三趟末尾字符和首字符都匹配，繼續(xù)向右移動距離為5。第四趟末尾字符不匹配，則為壞字符向右移動3位。第五趟匹配成功結(jié)束。

3.3.2改進的BM算法描述

改進的BM算法對BM算法添加了一個開頭的概念，考慮到從末尾開始匹配時匹配了很多字符然而開始字符卻沒有匹配，就造成了無用匹配。改算法執(zhí)行的步驟如下描述：

a)將模式串P和文本串T對齊，比較末尾字符和首字符即P[m-1]和T[j+m]，P[0]和T[j]。

b)當P[m-1]=T[j+m]，P[0]≠T[j]時，模式串P向右移動1位。

c)當P[0]=T[j]時，不論P[m-1]等于或者不等于T[j+m]，自右向左開始匹配，如果出現(xiàn)壞字符與P[i]不匹配，向右移動dist[i]個距離。匹配成功則退出。

設(shè)slide為改進的BM算法滑動距離函數(shù)，它的單位是一個字符長度，如下所示：

改進的BM算法減少了對已知該目標字符串不匹配時的回溯比較次數(shù)，從而使總的比較次數(shù)減少，以提高匹配效率。例如在表1中BM算法的字符的比較次數(shù)為14次，改進后的比較次數(shù)為10次。第一趟過程中當首字符出現(xiàn)了不匹配，即前5個字符已經(jīng)匹配失效了，但是按照BM算法從后向前比較需要比較5次，因為后面幾個字符都相同。所以這里后面這幾個字符的4次比較就是多余的。改進后只需要匹配1次即可，對于同時比較首字符和末尾字符這樣可以根據(jù)原來的BM算法算出移動距離，減少匹配次數(shù)。

4　結(jié)　語

改進的BM算法綜合3傳統(tǒng)的BM算法高效率的優(yōu)點，解決了只有好后綴沒有好開頭的情況，減少了匹配次數(shù)，提高了匹配效率。由于在linux文件查找的過程中文件的絕對路徑名稱并不是很長，所以比較尾部同時又比較開頭，使得linux的locate命令在文件查找的時候速度更快，提高用戶體驗。

[1]尹泉.淺談嵌入式系統(tǒng)設(shè)計及發(fā)展趨勢[J].計算機光盤軟件以及應用，2014,17(2):253-254.

[2]毛德操，胡希明.LINUX內(nèi)核源代碼情景分[M].杭州：浙江大學出版社，2001:530-534.

[3]段海夢.Linux文件系統(tǒng)解析與模擬[J].網(wǎng)絡安全技術(shù)與應用，2014(8): 30-32.

[4]GOSCINSKIA.Twoalgorithmsformutualexclusioninreal-timedistributedcomputersystems[J].JournalofParallelandDistributedComputing,1990,9(1):77-82.

[5]嚴蔚敏，吳偉明.數(shù)據(jù)結(jié)構(gòu)：C語言版[M].北京:清華大學出版社，1999:60-81.

[6]閔聯(lián)營，趙婷婷.BM算法的研究與改進[J].武漢理工大學學報，2006,30(3):529-530.

[7]BOYERRS,MOOREJS.Afaststringsearchingalgorithm[J].CommunicationsoftheACM,1977,20(10):762-772.

[8]阮一峰.字符串匹配的Boyer-Moore算法[EB/OL].(2013-05-03)[2015-07-26].http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html.2013-05-03.

[9]韓光輝，曾誠.Boyer-Moore串匹配算法的改進[J].計算機應用，2014,34(3):865-868.

[10]郝爽.BM算法中好后綴規(guī)則的研究[J].科技信息，2007(36):539-540.

(責任編輯： 陳和榜)

Command Parsing of File Searching and Query Optimization of Locate Command in Linux

WANGWeiwei，LIRenwang，ZHAOYaping，WANGHaizhou，SONGShengtao

(1.Faculty of Mechanical Engineering & Automation, Zhejiang Sci-Tech University, Hangzhou 310018, China; 2.College of life science, Nanjing Normal University, Nanjing 210046, China)

Linux system has been widely used recently. Users often use command line to operate the system as well as find the files; especially, when the linux system is used as a server, one often spends much time in finding the file needed in a large number of files. In order to find the file needed quickly, we analyze the implementation principles and process of two existing linux file search commands; besides, after analyzing the famous Boyer Moore - string matching algorithm, we used the improved algorithm of BM to optimize the string matching algorithm in locate command, a kind of search command. Based on the analysis on complexity of the improved algorithm, it has higher efficiency and a faster query speed in the string matching process of filename, compared with the former KMP algorithm.

Linux file search; find command; locate command; BM algorithm; updatedb command

10.3969/j.issn.1673-3851.2016.05.015

2015-07-26

國家自然科學基金項目(51475434)

王維維(1991-)，男，安徽廣德縣人，碩士研究生，主要從事機械制造及其自動化方面的研究。

李仁旺，E-mail：renwangli@zstu.edu.cn

TP3-05

A

1673- 3851 (2016) 03- 0409- 05 引用頁碼： 050603