2007年9月12日
反向索引：
正向索引（草稿，不完全，因為收到field info的影響，不同的field存儲內容不同，且fieldInfo的有些信息,TOKENIZED BINARY COMPRESSED也是保存在.fdt的每個document相關段的bits中,而不是.fnm中）:
Lucene在1.9版本的時候就已經加入了對GCJ的支持，利用GCJ編譯Lucene，并且使用新的GCJIndexInput.java讀寫文件系統(tǒng)，
直接調用操作系統(tǒng)級別的native方法，相信讀寫性能能夠極大得提高啊。
具體代碼可見Lucene的gcj目錄，編譯使用ant gcj
說明見Similarity.java的javadoc信息：
算法請參考javadoc的，它使用的是Vector Space Model (VSM) of Information Retrieval。
針對一條查詢語句q(query)，一個d(document)的得分公式
其中，
tf(t in d) 表示某個term的出現頻率，定義了term t出現在當前地document d的次數。 那些query中給定地term，如果出現越多次的，得分越高 。它在默認實現DefaultSimilarity的公式為
idf(t) 表示反向文檔頻率。這個參數表示docFreq(term t一共在多少個文檔中出現)的反向影響值。它意味著在越少文檔中出現的terms貢獻越高地分數。它在默認實現DefaultSimilarity的公式為:
idf(t) = |
1 + log ( |
| numDocs |
| ––––––––– |
| docFreq+1 |
|
) |
coord(q,d) 是一個基于在該文檔中出現了多少個query中的terms的得分 因素。文檔中出現的query中的terms數量/query總共多少個query數量。典型的，一個文檔包含越多地query中的terms會得到更高地分。This is a search time factor computed in coord(q,d) by the Similarity in effect at search time.
queryNorm(q) 是一個標準化參數，它是用來區(qū)分比較不同queries時的因素，這個因素不影響document ranking (因為所有的ranked document都會乘以相同的值)，但是不同地queries（或這不同地indexes中）它會得到不同的可用于比較的值。This is a search time factor computed by the Similarity in effect at search time. 它在默認實現DefaultSimilarity的公式為:
其中的sumOfSquaredWeights(of the query terms)是根據the query Weight object計算出來的. For example, a boolean query computes this value as:
t.getBoost() 是一個term t在query q中的search time boost， 它是在the query text (see query syntax)中指定的, 或者被應用程序直接調用 setBoost()設置的. 注意，這兒沒有直接的API去訪問在 a multi term query的一個term的boost值，但是multi terms會以multi TermQuery objects在一個query中被表示,因此the boost of a term in the query可以使用子query的 getBoost()反問到.
norm(t,d) 封裝(encapsulates)了一些(indexing time)的boost和length factors: ???這個參數之和field中tokens的數量有關，和term本身無關???
Document boost - set by calling doc.setBoost() before adding the document to the index.
Field boost - set by calling field.setBoost() before adding the field to a document.
lengthNorm(field) -。當文檔被加入到索引時計算，，和document的field 中的tokens的數量有關，因此，一個比較短的fields貢獻更高的分數。LengthNorm is computed by the Similarity class in effect at indexing. DefaultSimilarity中的實現為(float)(1.0 / Math.sqrt(numTerms));
當一個文檔被加入索引時，上述因素會被相乘。如果文檔有多個fields同名，他們的boosts數值會被多次相乘。
但是 ，計算出的norm數值在存儲時是使用一個a single byte編碼的。search時，這個norm byte從index directory讀取，并且被解碼回float。這個編碼/解碼算法會產生精度丟失。 - it is not guaranteed that decode(encode(x)) = x. For instance, decode(encode(0.89)) = 0.75. Also notice that search time is too late to modify this norm part of scoring, e.g. by using a different Similarity for search.
Lucene的索引文件，會包含很多個segments文件，每個segment中包含多個documents文件，一個segment中會有完整的正向索引和反向索引。
在搜索時，Lucene會遍歷這些segments，以segments為基本單位獨立搜索每個segments文件，而后再把搜索結果合并。
建立索引文件的過程，實際就是把documents文件一個個加入索引中，Lucene的做法是最開始為每個新加入的document獨立生成一個segment，放在內存中。而后，當內存中segments數量到達一個闕值時，合并這些segments，新生成一個segment加入文件系統(tǒng)的segments列表中。
而當文件系統(tǒng)的segments數量過多時，勢必影響搜索效率，因此需要不斷合并這些segments文件。
那么Lucene的合并策略是什么？如何保證合適的segments數量呢？
其實Lucene有兩套基本的策略：
第一種策略實現代碼位于IndexWriter#optimize()函數，其實就是把所有segments文件合并成一個文件。合并的算法是遞歸合并列表最后的mergeFactor個segments文件直到合并成一個文件。這兒mergeFactor是Lucene的一個參數。
btw: 從算法細節(jié)上看，其實我不是喜歡這段實現，因為列表的最后mergeFactor個文件內容實際被掃描了segmens_count/mergeFactor次。如果分段歸納合并的方式不知道是否更好，每個segment文件內容都將被掃描 ceil(Log_mergeFactor(segmens_count)) 或ceil(Log_mergeFactor(segmens_count)) +1次，是否更好?
第二種策略實現代碼位于IndexWriter#maybeMergeSegments()函數中，這個代碼就復雜了，它的基本策略就是要求確保合并后兩個公式的成立:
假定segments是個有序列表，B表示maxBufferedDocs，f(n)=ceil(log_M(ceil(n/B)))，M表示mergeFactor，這兒maxBufferedDocs和mergeFactor是兩個參數
1. 如果第i個segment的documents數量為x，第i+1個segment的documents數量為y，那么f(x)>f(y)一定成立
2. f(n)值相同的segments的數量不得超過M。
那么maybeMergeSegments()函數是如何確保這兩個公式成立的呢?
1.首先，從代碼：
protected final void maybeFlushRamSegments() throws IOException {
// A flush is triggered if enough new documents are buffered or
// if enough delete terms are buffered
if (ramSegmentInfos.size() >= minMergeDocs
|| numBufferedDeleteTerms >= maxBufferedDeleteTerms) {
flushRamSegments();
}
}
這兒minMergeDocs=maxBufferedDocs, 因此可以看出，當內存中緩存的segments被合并寫回磁盤時生成的segment的document count等于或小于maxBufferedDocs（即minMergeDocs）。
補充：因為maybeMergeSegments()運行在同步代碼中，因此只要ramSegmentInfos.size==minMergerDocs(即maxBufferedDocs)就會寫回磁盤，因此應該不存在ramSegmentInfos.size>maxBufferedDocs才寫回的情況。而且，但如果是這種情況，因為合并后的segment文件的document count過大，后面的maybeMergeSegments()將不做合并處理直接退出，上述公式就可能不成立，那么算法將有錯。
----
2.
2.1 因此maybeMergeSegments()第一次執(zhí)行時，所有segments的document count都小于等于maxBufferedDocs。此時，從i=0開始，合并i~i+mergeFactor-1個文件，如果合并后的doc count>maxBufferedDocs時，保留第i個segment，否則繼續(xù)合并改變后的i~i+mergeFactor-1，直到doc count>maxBufferedDocs或所有segments文件個數已經<mergeFactor了。經過這樣一輪的合并，除了最后<mergeFactor個的doc counts<=maxBufferedDocs文件外，其它文件的doc counts一定都>maxBufferedDocs并<maxBufferedDocs*mergeFactor了。
2.2 這時，不理會最后<mergeFactor個doc count<maxBufferedDocs的文件，而后按2.1的同理規(guī)則，合并之前的文件，讓這些文件的最后<mergerFactor個segment符合 maxBufferedDocs<doc counts<=maxBufferedDocs*mergeFactor，之前的segment文件都符合maxBufferedDocs*mergeFactor<doc counts<=maxBufferedDocs*mergeFactor^2
2.3 重復2.2，最后得到的列表就會滿足上述兩等式的成立
---
3
之后，每次從內存緩存中flush出一個新的segment時，也就是往這個segments列表的最后增加一個doc_count<=maxBufferedDocs的文件，同樣執(zhí)行上述步驟2進行合并，能夠始終保證上述兩公式的成立。
----
4
4.1
IndexWriter#addIndexesNoOptimize同樣借鑒使用了maybeMergeSegments()算法，區(qū)別此時，實際是已有一個符合兩公式的segments序列T，在T之后追加上隨意順序的segments序列S。這時，我們先找到S中doc count值最大的那個segment，計算出它屬于的區(qū)間f(x)，使得maxBufferedDocs*mergeFactor^x<doc counts<=maxBufferedDocs*mergeFactor^(x+1)，而后按2.2的算法合并出除了最后<mergerFactor個segments外， 之前所有segments都符合 a. doc count>maxBufferedDocs*mergeFactor^(x+1) b.符合上述2等式。
btw: 因為這兒調用IndexWriter#addIndexesNoOptimize傳入的參數是maxBufferedDocs*mergeFactor^(x+1)，因為S所有segment的doc count都一定小于maxBufferedDocs*mergeFactor^(x+1)，因此S的所有元素都會參與收縮合并。
4.2 將最后<mergerFactor個doc count<maxBufferedDocs*mergeFactor^(x+1)的segments合并，如果合并后的segment的doc count大于maxBufferedDocs*mergeFactor^(x+1)，就繼續(xù)2.2步驟，使得整個隊列符合上述兩公式
-----
上述兩種策略，最終確保了Lucene中的segments不會太多,確保效率。
BTW：實際上，如果documents太多時，Lucene還支持把docuements分成幾個組，每個組用獨立的進程或電腦進行索引，而后再多個目錄的索引合并起來，具體可參考IndexWriter#addIndexesNoOptimize和IndexWriter#addIndexes函數
FieldSelectorResult:枚舉，分別為
LOAD Document#getFieldable和Document#getField不會返回null
LAZY_LOAD :Lazy的Field意味著在搜索結果里這個Field的值缺省是不讀取的，只有當你真正對這個Field取值的時候才會去取。所以如果你要對它取值，你得保證IndexReader還沒有close。 Document#getField不能使用，只能使用Document#getFieldable
NO_LOAD Document#getField和Document#getFieldable都返回null，Document#add不被調用。
LOAD_AND_BREAK 類似LOAD，Document#getField和Document#getFieldable都可用，但返回后就結束，Document可能沒有完整的field的Set，參考LoadFirstFieldSelector 。
LOAD_FOR_MERGE 類似LOAD，但不壓縮任何數據。只被SegmentMerger的一個FieldSelector匿名內嵌實現類使用。Document#getField和Document#getFieldable可返回null.
SIZE 返回Field的size而不是value. Size表示存儲這個field需要的bytes數，string數值使用2*chars。size被存儲為a binary value，表現為as an int in a byte[]，with the higher order byte first in [0]。
SIZE_AND_BREAK 類似SIZE，但立刻break from the field loading loop, i.e. stop loading further fields, after the size is loaded
======================================
Field中三大enum: Store Index和TermVector：
------------------------------------
Store.COMPRESS Store the original field value in the index in a compressed form. This is useful for long documents and for binary valued fields.壓縮存儲；
Store.YES Store the original field value in the index. This is useful for short texts like a document's title which should be displayed with the results. The value is stored in its original form, i.e. no analyzer is used before it is stored. 索引文件本來只存儲索引數據, 此設計將原文內容直接也存儲在索引文件中，如文檔的標題。
Store.NO Do not store the field value in the index. 原文不存儲在索引文件中，搜索結果命中后，再根據其他附加屬性如文件的Path，數據庫的主鍵等，重新連接打開原文，適合原文內容較大的情況。
決定了Field對象的 this.isStored 和 this.isCompressed
------------------------------------
Index.NO Do not index the field value. This field can thus not be searched, but one can still access its contents provided it is Field.Store stored. 不進行索引，存放不能被搜索的內容如文檔的一些附加屬性如文檔類型, URL等。
Index.TOKENIZED Index the field's value so it can be searched. An Analyzer will be used to tokenize and possibly further normalize the text before its terms will be stored in the index. This is useful for common text. 分詞索引
Index.UN_TOKENIZED Index the field's value without using an Analyzer, so it can be searched. As no analyzer is used the value will be stored as a single term. This is useful for unique Ids like product numbers. 不分詞進行索引，如作者名，日期等，Rod Johnson本身為一單詞，不再需要分詞。
Index.NO_NORMS 不分詞，建索引。norms是什么???字段值???。但是Field的值不像通常那樣被保存，而是只取一個byte，這樣節(jié)約存儲空間???? Index the field's value without an Analyzer, and disable the storing of norms. No norms means that index-time boosting and field length normalization will be disabled. The benefit is less memory usage as norms take up one byte per indexed field for every document in the index.Note that once you index a given field <i>with</i> norms enabled, disabling norms will have no effect. In other words, for NO_NORMS to have the above described effect on a field, all instances of that field must be indexed with NO_NORMS from the beginning.
決定了Field對象的 this.isIndexed this.isTokenized this.omitNorms
------------------------------------
Lucene 1.4.3新增的：
TermVector.NO Do not store term vectors. 不保存term vectors
TermVector.YES Store the term vectors of each document. A term vector is a list of the document's terms and their number of occurences in that document. 保存term vectors。
TermVector.WITH_POSITIONS Store the term vector + token position information 保存term vectors。（保存值和token位置信息）
TermVector.WITH_OFFSETS Store the term vector + Token offset information
TermVector.WITH_POSITIONS_OFFSETS Store the term vector + Token position and offset information 保存term vectors。（保存值和Token的offset）
決定了Field對象的this.storeTermVector this.storePositionWithTermVector this.storeOffsetWithTermVector
以下內容均為轉載,url見具體鏈接:
最常見的四個Analyzer,說明: http://windshowzbf.bokee.com/3016397.html
WhitespaceAnalyzer 僅僅是去除空格，對字符沒有l(wèi)owcase化,不支持中文
SimpleAnalyzer :功能強于WhitespaceAnalyzer,將除去letter之外的符號全部過濾掉,并且將所有的字符lowcase化,不支持中文
StopAnalyzer: StopAnalyzer的功能超越了SimpleAnalyzer，在SimpleAnalyzer的基礎上.增加了去除StopWords的功能,不支持中文.類中使用一個static數組保存了ENGLISH_STOP_WORDS, 太常見不index的words
StandardAnalyzer: 用Javacc定義的一套EBNF，嚴禁的語法。有人說英文的處理能力同于StopAnalyzer.支持中文采用的方法為單字切分。未仔細比較，不敢確定。
其他的擴展:
ChineseAnalyzer:來自于Lucene的sand box.性能類似于StandardAnalyzer,缺點是不支持中英文混和分詞.
CJKAnalyzer:chedong寫的CJKAnalyzer的功能在英文處理上的功能和StandardAnalyzer相同.但是在漢語的分詞上，不能過濾掉標點符號，即使用二元切分
TjuChineseAnalyzer: http://windshowzbf.bokee.com/3016397.html寫的,功能最為強大.TjuChineseAnlyzer的功能相當強大,在中文分詞方面由于其調用的為ICTCLAS的java接口.所以其在中文方面性能上同與ICTCLAS.其在英文分詞上采用了Lucene的StopAnalyzer,可以去除 stopWords,而且可以不區(qū)分大小寫,過濾掉各類標點符號.
例子:
http://www.langtech.org.cn/index.php/uid-5080-action-viewspace-itemid-68, 還有簡單的代碼分析
Analyzing "The quick brown fox jumped over the lazy dogs"
WhitespaceAnalyzer:
[The] [quick] [brown] [fox] [jumped] [over] [the] [lazy] [dogs]
SimpleAnalyzer:
[the] [quick] [brown] [fox] [jumped] [over] [the] [lazy] [dogs]
StopAnalyzer:
[quick] [brown] [fox] [jumped] [over] [lazy] [dogs]
StandardAnalyzer:
[quick] [brown] [fox] [jumped] [over] [lazy] [dogs]
Analyzing "XY&Z Corporation - xyz@example.com"
WhitespaceAnalyzer:
[XY&Z] [Corporation] [-] [xyz@example.com]
SimpleAnalyzer:
[xy] [z] [corporation] [xyz] [example] [com]
StopAnalyzer:
[xy] [z] [corporation] [xyz] [example] [com]
StandardAnalyzer:
[xy&z] [corporation] [xyz@example.com]
參考連接:
http://macrochen.blogdriver.com/macrochen/1167942.html
http://macrochen.blogdriver.com/macrochen/1153507.html
http://my.dmresearch.net/bbs/viewthread.php?tid=8318
http://windshowzbf.bokee.com/3016397.html
推薦
http://gceclub.sun.com.cn/developer/technicalArticles/Intl/Supplementary/index_zh_CN.html
http://www.linuxpk.com/3821.html
=======================================
BMP的解釋：
http://zh.wikipedia.org/w/index.php?title=%E5%9F%BA%E6%9C%AC%E5%A4%9A%E6%96%87%E7%A8%AE%E5%B9%B3%E9%9D%A2&variant=zh-cn
http://zh.wikipedia.org/w/index.php?title=%E8%BE%85%E5%8A%A9%E5%B9%B3%E9%9D%A2&variant=zh-cn#.E7.AC.AC.E4.B8.80.E8.BC.94.E5.8A.A9.E5.B9.B3.E9.9D.A2
1個BMP和16個輔助plane，需要21個bits.
======================================
ISO-10646與Unicode關系
http://zh.wikipedia.org/wiki/%E9%80%9A%E7%94%A8%E5%AD%97%E7%AC%A6%E9%9B%86
ISO-10646術語
|
Unicode術語
|
| UCS-2 |
BMP UTF-16 |
| UCS-4 |
UTF-32 |
|
|
注意：UTF-16可看成是UCS-2的 父集。在沒有輔助平面字符前，UTF-16與UCS-2所指的是同一的意思。但當引入輔助平面字符後，就只稱為UTF-16了，因為我們會使用2個UTF-16，也就似乎4bytes保存一個輔助平面字符。現在若有軟件聲稱自己支援UCS-2編碼，那其實是暗指它不能支援輔助平面字符的委婉語。
======================================
UTF-8要完整表達unicode需要4bytes，表達BMP需要3bytes，見 http://en.wikipedia.org/wiki/UTF-8，注意“The range D800-DFFF is disallowed by Unicode. The encoding scheme reliably transforms values in that range, but they are not valid scalar values in Unicode. See Table 3-7 in the Unicode 5.0 standard. ”
======================================
BOM Byte Order Mark，在UCS編碼中有一個叫做"ZERO WIDTH NO-BREAK SPACE"的字符，它的編碼是FEFF。而FFFE在UCS中是不存在的字符，所以不應該出現在實際傳輸中。UCS規(guī)范建議我們在傳輸字節(jié)流前，先傳輸字符"ZERO WIDTH NO-BREAK SPACE"。
這樣如果接收者收到FEFF，就表明這個字節(jié)流是Big-Endian的；如果收到FFFE，就表明這個字節(jié)流是Little-Endian的。
字符"ZERO WIDTH NO-BREAK SPACE"又被稱作BOM。UTF-8不需要BOM來表明字節(jié)順序，但可以用BOM來表明編碼方式。字符"ZERO WIDTH NO-BREAK SPACE"(也就是U+FEFF)的UTF-8編碼是EF BB BF（就是11101111,10111011,10111111）。所以如果接收者收到以EF BB BF開頭的字節(jié)流，就知道這是UTF-8編碼了。
Windows就是使用BOM來標記文本文件的編碼方式的。
除了FEFF，英文wiki http://en.wikipedia.org/wiki/UTF-8還解釋說明了一些目前不會出現在utf-8字節(jié)流中的byte值。
=========================================
Java
http://www.jorendorff.com/articles/unicode/java.html
http://gceclub.sun.com.cn/developer/technicalArticles/Intl/Supplementary/index_zh_CN.html 完美解釋java中的unicode。另外提到java中utf-8其實有兩種格式，分別是標準utf-8和改良utf-8。對于文本輸入， Java 2 SDK 提供用于接受“\Uxxxxxx”格式字符串的代碼點輸入方法，這里大寫的“U”表示轉義序列包含六個十六進制數字，因此允許使用增補字符。小寫的“u”表示轉義序列“\uxxxx”的原始格式。
http://dlog.cn/html/diary/showlog.vm?sid=2&cat_id=-1&log_id=557 介紹了String的JDK5新增方法
http://blog.csdn.net/qinysong/archive/2006/09/05/1179480.aspx 連著三篇用實例說明，語言比較亂，說的也不盡正確，但他用了做試驗的java代碼有點意思，能幫助思考代碼中一些tricky的現象。
http://topic.csdn.net/u/20070928/22/5207088c-c47d-43ed-8416-26f850631cff.html 有一些回答，
http://topic.csdn.net/u/20070515/14/57af3319-28de-4851-b4cf-db65b2ead01c.html 有些試驗代碼，價值不大
http://www.w3china.org/blog/more.asp?name=hongrui&id=24817 有些java實例代碼，沒細看。
另：
Java 1.0 supports Unicode version 1.1.
Java 1.1 onwards supports Unicode version 2.0.
J2SE 1.4中的字符處理是基于Unicode 3.0標準的。
J2SE v 1.5 supports Unicode 4.0 character set.
而：
Unicode 3.0：1999年九月；涵蓋了來自ISO 10646-1的十六位元通用字元集（UCS）基本多文種平面（Basic Multilingual Plane）
Unicode 3.1：2001年三月；新增從ISO 10646-2定義的輔助平面（Supplementary Planes)
所以：
代碼點在U+0000到U+FFFF之間的就用\u0000到\uffff表示
U+10000到U+1FFFF之間的用 \ud800到\udbff中的作為第一個單元, 用\udc00到\udfff作為第二單元,組合起來表示
char這個概念就是指\u0000到\uffff,這是占兩個字節(jié)
其余的用code point這個概念
JDK 1.5 以上支持 Unicode 4.0，也就是 Unicode 的范圍是 U+0000～U+10FFFF，
超過 U+FFFF 的字符采用代碼點（也就是 int 類型的數據）來表示，具體的可以
參考一下下面這個鏈接的文章《Java 平臺中的增補字符》，對此作了很詳細的介
紹。 http://gceclub.sun.com.cn/developer/technicalArticles/Intl/Supplementary/index_zh_CN.html
================================
http://m.tkk7.com/tim-wu/archive/2007/09/12/144550.html
================================
| U-00000000 - U-0000007F: |
0xxxxxxx |
| U-00000080 - U-000007FF: |
110xxxxx 10xxxxxx |
| U-00000800 - U-0000FFFF: |
1110xxxx 10xxxxxx 10xxxxxx |
| U-00010000 - U-001FFFFF: |
11110xxx 10xxxxxx 10xxxxxx 10xxxxxx |
| U-00200000 - U-03FFFFFF: |
111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx |
| U-04000000 - U-7FFFFFFF: |
1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx |
但目前ISO和Unicode組織都不會規(guī)定10FFFF以上的字符
代碼範圍
十六進制 |
標量值(scalar value
二進制 |
UTF-8
二進制 / 十六進制 |
註釋 |
000000 - 00007F
128個代碼 |
00000000 00000000 0zzzzzzz |
0zzzzzzz(00-7F) |
ASCII等值範圍，位元組由零開始 |
| 七個z |
七個z |
000080 - 0007FF
1920個代碼 |
00000000 00000yyy yyzzzzzz |
110yyyyy(C2-DF) 10zzzzzz(80-BF) |
第一個位元組由110開始，接著的位元組由10開始 |
| 三個y；二個y；六個z |
五個y；六個z |
000800 - 00FFFF
63488個代碼 |
00000000 xxxxyyyy yyzzzzzz |
1110xxxx(E0-EF) 10yyyyyy 10zzzzzz |
第一個位元組由1110開始，接著的位元組由10開始 |
| 四個x；四個y；二個y；六個z |
四個x；六個y；六個z |
010000 - 10FFFF
1048576個代碼 |
000wwwxx xxxxyyyy yyzzzzzz |
11110www(F0-F4) 10xxxxxx 10yyyyyy 10zzzzzz |
由11110開始，接著的位元組由10開始 |
| 三個w；二個x；四個x；四個y；二個y；六個z |
三個w；六個x；六個y；六個z |
================================
參考：http://blog.csdn.net/qinysong/archive/2006/09/05/1179480.aspx，但該文對unicode版本說明有誤，說明見上
在大約 1993 年之后開發(fā)的大多數現代編程語言都有一個特別的數據類型, 叫做 Unicode/ISO 10646-1 字符. 在 Ada95 中叫 Wide_Character, 在 Java 中叫 char.
ISO C 也詳細說明了處理多字節(jié)編碼和寬字符 (wide characters) 的機制, 1994 年 9 月 Amendment 1 to ISO C 發(fā)表時又加入了更多. 這些機制主要是為各類東亞編碼而設計的, 它們比處理 UCS 所需的要健壯得多. UTF-8 是 ISO C 標準調用多字節(jié)字符串的編碼的一個例子, wchar_t 類型可以用來存放 Unicode 字符.
代碼為QueryParser.jj，語法為JavaCC實現的LL()：
完整文檔：http://lucene.apache.org/java/2_0_0/queryparsersyntax.html
和正則一樣：
?表示0個或1個
+表示一個或多個
*表示0個或多個
以下是Token部分：
_NUM_CHAR::=["0"-"9"] //數字
_ESCAPED_CHAR::= "\\" [ "\\", "+", "-", "!", "(", ")", ":", "^", "[", "]", "\"", "{", "}", "~", "*", "?" ] > //特殊字符，
_TERM_START_CHAR ::=( ~[ " ", "\t", "\n", "\r", "+", "-", "!", "(", ")", ":", "^","[", "]", "\"", "{", "}", "~", "*", "?" ] //TERM的起始字符，除了列出的其它字符都可以
_TERM_CHAR::=( <_TERM_START_CHAR> | <_ESCAPED_CHAR> | "-" | "+" ) > //TERM可使用字符
_WHITESPACE::= ( " " | "\t" | "\n" | "\r") //空格和回車，
<DEFAULT> TOKEN:
AND::=("AND" | "&&")
OR::=("OR" | "||")
NOT::=("NOT" | "!")
PLUS::="+"
MINUS::="-"
LPAREN::="("
RPAREN::=")"
COLON::=":"
STAR::="*"
CARAT::="^" //后接Boost，原文<CARAT: "^" > : Boost，后面Boost說明什么沒明白
QUOTED::="\"" (~["\""] | "\\\"")+ "\"" // 表示用"包起來的字符串,字符"開始，中間由不是"的符號或者連著的這兩個符號\"組成，字符"結束，
TERM::=<_TERM_START_CHAR> (<_TERM_CHAR>)*
FUZZY_SLOP::="~" ( (<_NUM_CHAR>)+ ( "." (<_NUM_CHAR>)+ )? )? //字符~開始，而后是數字.Lucene支持模糊查詢，例如"roam~"或"roam~0.8"，The value is between 0 and 1，算法為the Levenshtein Distance, or Edit Distance algorithm
PREFIXTERM::=(<_TERM_START_CHAR> | "*") (<_TERM_CHAR>)* "*" > //模糊查找，表示以某某開頭的查詢, 字符表示為"something*"，前綴允許模糊符號*，中間可有字符也可沒有， 結尾必須是*
WILDTERM::=(<_TERM_START_CHAR> | [ "*", "?" ]) (<_TERM_CHAR> | ( [ "*", "?" ] ))* > //類似上面，但同時支持?字符，結尾可以是字符也可以是* ?。使用[]表示or關系時，不需要使用|，只要,號分割即可
RANGEIN_START::="[" //在RangeQuery中，[或{表示了是否包含邊界條件本身, 用字符表示為"[begin TO end]" 或者"{begin TO end}",后接RangeIn
RANGEEX_START::="{" //同上，后接RangeEx
<Boost> TOKEN:
NUMBER::=(<_NUM_CHAR>)+ ( "." (<_NUM_CHAR>)+ )? //后接DEFAULT， 整數或小數
<RangeIn> TOKEN:
RANGEIN_TO::="TO"
RANGEIN_END::="]" //后接DEFAULT, RangIn的結束
RANGEIN_QUOTED::= "\"" (~["\""] | "\\\"")+ "\"" //同上述QUOTED，表示用"包起來的字符串,
RANGEIN_GOOP::= (~[ " ", "]" ])+ //1個或多個不是空格和]的符號,這樣就能提取出[]中的內容
<RangeEx> TOKEN :
RANGEEX_TO::="TO">
RANGEEX_END::="}" //后接DEFAULT, RangeEx的結束
RANGEEX_QUOTED::="\"" (~["\""] | "\\\"")+ "\"" //同上述QUOTED，表示用"包起來的字符串,
RANGEEX_GOOP::=(~[ " ", "}" ])+ //1個或多個不是空格和]的符號,這樣就能提取出[]中的內容
<DEFAULT, RangeIn, RangeEx> SKIP : {
< <_WHITESPACE>>
} //所有空格和回車被忽略
以下為解析部分
Conjunction::=[ <AND> { ret = CONJ_AND; } | <OR> { ret = CONJ_OR; } ] //連接
Modifiers::=[ <PLUS> { ret = MOD_REQ; } | <MINUS> { ret = MOD_NOT; } | <NOT> { ret = MOD_NOT; } ] //+ - !符號
Query::=Modifiers Clause (Conjunction Modifiers Clause)*
Clause::=[(<TERM> <COLON>|<STAR> <COLON>)] //btw:代碼中LOOKAHEAD[2]表示使用LL(2)
(Term|<LPAREN> Query <RPAREN> (<CARAT> <NUMBER>)?) //子句. ???????這兒語法有點,仿佛允許 *:(*:dog)這樣的語法,很奇怪
Term::=(
(<TERM>|<STAR>|<PREFIXTERM>|<WILDTERM>|<NUMBER>) [<FUZZY_SLOP>] [<CARAT><NUMBER>[<FUZZY_SLOP>]}
| ( <RANGEIN_START> (<RANGEIN_GOOP>|<RANGEIN_QUOTED>) [ <RANGEIN_TO> ] (<RANGEIN_GOOP>|<RANGEIN_QUOTED> <RANGEIN_END> ) [ <CARAT> boost=<NUMBER> ] //這兒看出range必須同時有兩端,不能只有有一端
| ( <RANGEEX_START> <RANGEEX_GOOP>|<RANGEEX_QUOTED> [ <RANGEEX_TO> ] <RANGEEX_GOOP>|<RANGEEX_QUOTED> <RANGEEX_END> )[ <CARAT> boost=<NUMBER> ] //在RangeQuery中，[或{表示了是否包含邊界條件本身, 用字符表示為"[begin TO end]" 或者"{begin TO end}",后接RangeIn
| <QUOTED> [ <FUZZY_SLOP> ] [ <CARAT> boost=<NUMBER> ] //被""包含的內容
btw: 猜測: javacc中,如果使用[],則允許出現0次或1次
今天讀了lucent中的PriorityQueue.java, 一個很巧妙的復雜度為log(n)的排序堆棧.
始終確保數組A[1...n]中:
A[i]<A[2*i] & A[i] < A[2*i +1]
很容易推論出A[1]一定是最小數值, 并且每次put()和pop()至多移動log(n)個數值
真是好久沒接觸算法了:)
ruby.exe提供了一個參數-r, 允許ruby在允許之前加載你指定的庫
1 如果你安裝了gem，那么環(huán)境變量RUBYOPT將為-rubygems，這個參數說明了ruby將提前加載ubygem.rb(注意，沒有r，不是rubygem.rb，而是ubygem:)
2 這時，如果你運行 ruby -e "puts $:"，可以查看到ruby查詢lib庫的目錄順序，其中第一個就是類似"..\ruby\site_ruby\1.8"目錄
3 因此，ubygem.rb將在ruby\site_ruby\1.8\ubygems.rb位置中被ruby定位到，而ubygem.rb只有一句話require 'rubygems'，這次才真正調用了rubygems.rb
4 接著rubygems.rb的最后一句require 'rubygems/custom_require'將加載custom_require.rb
5 最后custom_require.rb中替換了原先的require()函數的實現，這之后，庫的加載，將遵循gem的目錄約定。
記得上學時學數據庫，書中說過：“數據庫建模一般實現到3NF和BCNF，4NF 5NF基本沒用”，造成多年對4NF和5NF置之不理。
離開學校7年后的今天，無事有把數據庫的范式定義拿起來翻翻，發(fā)覺好象我對4NF和5NF的理解一直有誤？
在做業(yè)務建模時，不少情況我們會盡可能地完全反映顯示業(yè)務關系，以 廠 采購員 和 訂單 為例：
如果業(yè)務認為訂單不屬于特定采購員，也即關系如下：
廠和訂單為1：n的關系；
廠和采購員也為1：n的關系；
采購員與訂單無關。
此時，那么我們肯定ORM簡單得處理為兩個關聯(lián)表，這時，不正是符合了4NF么？（如果只建立一個關聯(lián)表，表中三個字段廠id,訂單id，采購員id，而后三個id組成聯(lián)合主鍵，那就是符合了BCNF但不符合4NF了）
而如果關系更復雜，一個訂單可以被多個采購員處理，一個訂單還可以同屬于多個廠共享，那么我們一定是建立三個關聯(lián)表，獨立記錄三者間互相的關系，這不就是遵循了5NF么？
今天注冊了個Google Code的項目，還是google code爽啊，夠簡單，
http://code.google.com/hosting/createProject 注冊一下就成功，不用得著什么審核
svn速度爆快，相比sf.net就是個牛車。
其它沒試，不評論，這兩點就足夠了。
不知道rubyforge怎么樣。
  final byte[] addBuffer(int size)  {
 byte[] buffer = new byte[size];
if (directory!=null)
  synchronized (directory) { // Ensure addition of buffer and adjustment to directory size are atomic wrt directory
buffers.add(buffer);
directory.sizeInBytes += size;
sizeInBytes += size;
 }
else
buffers.add(buffer);
return buffer;
 }
今天讀了 http://infolab.stanford.edu/~backrub/google.html 一文，發(fā)現我畢業(yè)那年（2000年）google已有如此成果。
PageRank or PR(A) can be calculated using a simple iterative algorithm, and corresponds to the principal eigenvector of the normalized link matrix of the web. Also, a PageRank for 26 million web pages can be computed in a few hours on a medium size workstation.
最酷的就是這句話了，真酷的algorithm啊，我想破頭想不出頭緒來達到這個效率。
呵呵,從wikipedia開始，發(fā)現很有意思的文章越來越多:)
http://en.wikipedia.org/wiki/HITS_algorithm
今天翻了util包，發(fā)現自己對float的匱乏知識，好在有偉大的wiki百科：
http://en.wikipedia.org/wiki/IEEE_754
很清楚得解釋了IEEE 754規(guī)范
可惜看不懂lucene對small float的結構定義。
如果按我的理解，似乎類SmallFloat的函數byteToFloat()和byte315ToFloat()有bug，通過編寫測試代碼：
SmallFloat.byte315ToFloat(Byte.parseByte("01111000", 2)得到的float值為0.5f，
但按照byte315ToFloat()函數的說明，"01111000"的mantissaBits尾數長度為3, zeroExponent為15，無負數，
而01111按IEEE 754規(guī)范，應該理解為1，所以01111000表達的數值應該為1.0×2^0=1，而不是0.5f
非常之tricky。
通過讀byte315ToFloat()函數實現，發(fā)現"01111000"轉換為32位值0,01111110,00000000000000000000000,
該值按IEEE 754規(guī)范的確為0.5f， 其中正負位為1位，指數(exponent)位為8位，尾數(mantissa)位為23位。
而在byteToFloat()和byte315ToFloat()的實現中，我們可以常看到作者將尾數位偏移24-mantissa位，
也就是說，他理解的IEEE 754規(guī)范中尾數位不是23位而是24位。
以上僅為我的猜測，因為還沒有看到byteToFloat()的具體使用環(huán)境。
而且通過測試代碼，發(fā)現byte和float對應關系：
10000,000==2.0f= 1*2^1
10001,000==8.0f=1*2^3
10010,000==32.0f=1*2^5
01111,000 = 0.5f = 1*2^-1
01110,000==0.125f= 1* 2^-3
完全看不出合理的small float的結構，tricky!!!
因為工作需要，今天開始學習lucene，
因為有可能以后要深入研究full text的搜索，決定暫時不看in action，
采用最愚笨的方法，直接爬代碼。憑借以前的門外漢理解一步一步爬吧，
不知道還能衍生出多少知識。
|
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 26 | 27 | 28 | 29 | 30 | 31 | 1 | | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | 9 | 10 | 11 | 12 | 13 | 14 | 15 | | 16 | 17 | 18 | 19 | 20 | 21 | 22 | | 23 | 24 | 25 | 26 | 27 | 28 | 29 | | 30 | 1 | 2 | 3 | 4 | 5 | 6 |
|
導航
統(tǒng)計
- 隨筆： 28
- 文章： 0
- 評論： 38
- 引用： 1
常用鏈接
留言簿(4)
我參與的團隊
隨筆檔案
搜索
最新評論
閱讀排行榜
評論排行榜
|
|