xref: /dokuwiki/inc/indexer.php (revision 8d557116a19d366c0f00592e4fa6250017295105) 
1<?php
2/**
3 * Functions to create the fulltext search index
4 *
5 * @license    GPL 2 (http://www.gnu.org/licenses/gpl.html)
6 * @author     Andreas Gohr <andi@splitbrain.org>
7 */
8
9if(!defined('DOKU_INC')) die('meh.');
10
11// set the minimum token length to use in the index (note, this doesn't apply to numeric tokens)
12if (!defined('IDX_MINWORDLENGTH')) define('IDX_MINWORDLENGTH',2);
13
14// Asian characters are handled as words. The following regexp defines the
15// Unicode-Ranges for Asian characters
16// Ranges taken from http://en.wikipedia.org/wiki/Unicode_block
17// I'm no language expert. If you think some ranges are wrongly chosen or
18// a range is missing, please contact me
19define('IDX_ASIAN1','[\x{0E00}-\x{0E7F}]'); // Thai
20define('IDX_ASIAN2','['.
21                   '\x{2E80}-\x{3040}'.  // CJK -> Hangul
22                   '\x{309D}-\x{30A0}'.
23                   '\x{30FD}-\x{31EF}\x{3200}-\x{D7AF}'.
24                   '\x{F900}-\x{FAFF}'.  // CJK Compatibility Ideographs
25                   '\x{FE30}-\x{FE4F}'.  // CJK Compatibility Forms
26                   ']');
27define('IDX_ASIAN3','['.                // Hiragana/Katakana (can be two characters)
28                   '\x{3042}\x{3044}\x{3046}\x{3048}'.
29                   '\x{304A}-\x{3062}\x{3064}-\x{3082}'.
30                   '\x{3084}\x{3086}\x{3088}-\x{308D}'.
31                   '\x{308F}-\x{3094}'.
32                   '\x{30A2}\x{30A4}\x{30A6}\x{30A8}'.
33                   '\x{30AA}-\x{30C2}\x{30C4}-\x{30E2}'.
34                   '\x{30E4}\x{30E6}\x{30E8}-\x{30ED}'.
35                   '\x{30EF}-\x{30F4}\x{30F7}-\x{30FA}'.
36                   ']['.
37                   '\x{3041}\x{3043}\x{3045}\x{3047}\x{3049}'.
38                   '\x{3063}\x{3083}\x{3085}\x{3087}\x{308E}\x{3095}-\x{309C}'.
39                   '\x{30A1}\x{30A3}\x{30A5}\x{30A7}\x{30A9}'.
40                   '\x{30C3}\x{30E3}\x{30E5}\x{30E7}\x{30EE}\x{30F5}\x{30F6}\x{30FB}\x{30FC}'.
41                   '\x{31F0}-\x{31FF}'.
42                   ']?');
43define('IDX_ASIAN', '(?:'.IDX_ASIAN1.'|'.IDX_ASIAN2.'|'.IDX_ASIAN3.')');
44
45/**
46 * Measure the length of a string.
47 * Differs from strlen in handling of asian characters.
48 *
49 * @author Tom N Harris <tnharris@whoopdedo.org>
50 */
51function wordlen($w){
52    $l = strlen($w);
53    // If left alone, all chinese "words" will get put into w3.idx
54    // So the "length" of a "word" is faked
55    if(preg_match('/'.IDX_ASIAN2.'/u',$w))
56        $l += ord($w) - 0xE1;  // Lead bytes from 0xE2-0xEF
57    return $l;
58}
59
60/**
61 * Write a list of strings to an index file.
62 *
63 * @author Tom N Harris <tnharris@whoopdedo.org>
64 */
65function idx_saveIndex($pre, $wlen, &$idx){
66    global $conf;
67    $fn = $conf['indexdir'].'/'.$pre.$wlen;
68    $fh = @fopen($fn.'.tmp','w');
69    if(!$fh) return false;
70    foreach ($idx as $line) {
71        fwrite($fh,$line);
72    }
73    fclose($fh);
74    if(isset($conf['fperm'])) chmod($fn.'.tmp', $conf['fperm']);
75    io_rename($fn.'.tmp', $fn.'.idx');
76    return true;
77}
78
79/**
80 * Append a given line to an index file.
81 *
82 * @author Andreas Gohr <andi@splitbrain.org>
83 */
84function idx_appendIndex($pre, $wlen, $line){
85    global $conf;
86    $fn = $conf['indexdir'].'/'.$pre.$wlen;
87    $fh = @fopen($fn.'.idx','a');
88    if(!$fh) return false;
89    fwrite($fh,$line);
90    fclose($fh);
91    return true;
92}
93
94/**
95 * Read the list of words in an index (if it exists).
96 *
97 * @author Tom N Harris <tnharris@whoopdedo.org>
98 */
99function idx_getIndex($pre, $wlen){
100    global $conf;
101    $fn = $conf['indexdir'].'/'.$pre.$wlen.'.idx';
102    if(!@file_exists($fn)) return array();
103    return file($fn);
104}
105
106/**
107 * Create an empty index file if it doesn't exist yet.
108 *
109 * FIXME: This function isn't currently used. It will probably be removed soon.
110 *
111 * @author Tom N Harris <tnharris@whoopdedo.org>
112 */
113function idx_touchIndex($pre, $wlen){
114    global $conf;
115    $fn = $conf['indexdir'].'/'.$pre.$wlen.'.idx';
116    if(!@file_exists($fn)){
117        touch($fn);
118        if($conf['fperm']) chmod($fn, $conf['fperm']);
119    }
120}
121
122/**
123 * Read a line ending with \n.
124 * Returns false on EOF.
125 *
126 * @author Tom N Harris <tnharris@whoopdedo.org>
127 */
128function _freadline($fh) {
129    if (feof($fh)) return false;
130    $ln = '';
131    while (($buf = fgets($fh,4096)) !== false) {
132        $ln .= $buf;
133        if (substr($buf,-1) == "\n") break;
134    }
135    if ($ln === '') return false;
136    if (substr($ln,-1) != "\n") $ln .= "\n";
137    return $ln;
138}
139
140/**
141 * Write a line to an index file.
142 *
143 * @author Tom N Harris <tnharris@whoopdedo.org>
144 */
145function idx_saveIndexLine($pre, $wlen, $idx, $line){
146    global $conf;
147    if(substr($line,-1) != "\n") $line .= "\n";
148    $fn = $conf['indexdir'].'/'.$pre.$wlen;
149    $fh = @fopen($fn.'.tmp','w');
150    if(!$fh) return false;
151    $ih = @fopen($fn.'.idx','r');
152    if ($ih) {
153        $ln = -1;
154        while (($curline = _freadline($ih)) !== false) {
155            if (++$ln == $idx) {
156                fwrite($fh, $line);
157            } else {
158                fwrite($fh, $curline);
159            }
160        }
161        if ($idx > $ln) {
162            fwrite($fh,$line);
163        }
164        fclose($ih);
165    } else {
166        fwrite($fh,$line);
167    }
168    fclose($fh);
169    if($conf['fperm']) chmod($fn.'.tmp', $conf['fperm']);
170    io_rename($fn.'.tmp', $fn.'.idx');
171    return true;
172}
173
174/**
175 * Read a single line from an index (if it exists).
176 *
177 * @author Tom N Harris <tnharris@whoopdedo.org>
178 */
179function idx_getIndexLine($pre, $wlen, $idx){
180    global $conf;
181    $fn = $conf['indexdir'].'/'.$pre.$wlen.'.idx';
182    if(!@file_exists($fn)) return '';
183    $fh = @fopen($fn,'r');
184    if(!$fh) return '';
185    $ln = -1;
186    while (($line = _freadline($fh)) !== false) {
187        if (++$ln == $idx) break;
188    }
189    fclose($fh);
190    return "$line";
191}
192
193/**
194 * Split a page into words
195 *
196 * Returns an array of word counts, false if an error occurred.
197 * Array is keyed on the word length, then the word index.
198 *
199 * @author Andreas Gohr <andi@splitbrain.org>
200 * @author Christopher Smith <chris@jalakai.co.uk>
201 */
202function idx_getPageWords($page){
203    global $conf;
204    $swfile   = DOKU_INC.'inc/lang/'.$conf['lang'].'/stopwords.txt';
205    if(@file_exists($swfile)){
206        $stopwords = file($swfile);
207    }else{
208        $stopwords = array();
209    }
210
211    $body = '';
212    $data = array($page, $body);
213    $evt = new Doku_Event('INDEXER_PAGE_ADD', $data);
214    if ($evt->advise_before()) $data[1] .= rawWiki($page);
215    $evt->advise_after();
216    unset($evt);
217
218    list($page,$body) = $data;
219
220    $body   = strtr($body, "\r\n\t", '   ');
221    $tokens = explode(' ', $body);
222    $tokens = array_count_values($tokens);   // count the frequency of each token
223
224    // ensure the deaccented or romanised page names of internal links are added to the token array
225    // (this is necessary for the backlink function -- there maybe a better way!)
226    if ($conf['deaccent']) {
227        $links = p_get_metadata($page,'relation references');
228
229        if (!empty($links)) {
230            $tmp = join(' ',array_keys($links));                // make a single string
231            $tmp = strtr($tmp, ':', ' ');                       // replace namespace separator with a space
232            $link_tokens = array_unique(explode(' ', $tmp));    // break into tokens
233
234            foreach ($link_tokens as $link_token) {
235                if (isset($tokens[$link_token])) continue;
236                $tokens[$link_token] = 1;
237            }
238        }
239    }
240
241    $words = array();
242    foreach ($tokens as $word => $count) {
243        $arr = idx_tokenizer($word,$stopwords);
244        $arr = array_count_values($arr);
245        foreach ($arr as $w => $c) {
246            $l = wordlen($w);
247            if(isset($words[$l])){
248                $words[$l][$w] = $c * $count + (isset($words[$l][$w]) ? $words[$l][$w] : 0);
249            }else{
250                $words[$l] = array($w => $c * $count);
251            }
252        }
253    }
254
255    // arrive here with $words = array(wordlen => array(word => frequency))
256
257    $index = array(); //resulting index
258    foreach (array_keys($words) as $wlen){
259        $word_idx = idx_getIndex('w',$wlen);
260        foreach ($words[$wlen] as $word => $freq) {
261            $wid = array_search("$word\n",$word_idx);
262            if(!is_int($wid)){
263                $wid = count($word_idx);
264                $word_idx[] = "$word\n";
265            }
266            if(!isset($index[$wlen]))
267                $index[$wlen] = array();
268            $index[$wlen][$wid] = $freq;
269        }
270
271        // save back word index
272        if(!idx_saveIndex('w',$wlen,$word_idx)){
273            trigger_error("Failed to write word index", E_USER_ERROR);
274            return false;
275        }
276    }
277
278    return $index;
279}
280
281/**
282 * Adds/updates the search for the given page
283 *
284 * This is the core function of the indexer which does most
285 * of the work. This function needs to be called with proper
286 * locking!
287 *
288 * @author Andreas Gohr <andi@splitbrain.org>
289 */
290function idx_addPage($page){
291    global $conf;
292
293    // load known documents
294    $page_idx = idx_getIndex('page','');
295
296    // get page id (this is the linenumber in page.idx)
297    $pid = array_search("$page\n",$page_idx);
298    if(!is_int($pid)){
299        $pid = count($page_idx);
300        // page was new - write back
301        if (!idx_appendIndex('page','',"$page\n")){
302            trigger_error("Failed to write page index", E_USER_ERROR);
303            return false;
304        }
305    }
306    unset($page_idx); // free memory
307
308    $pagewords = array();
309    // get word usage in page
310    $words = idx_getPageWords($page);
311    if($words === false) return false;
312
313    if(!empty($words)) {
314        foreach(array_keys($words) as $wlen){
315            $index = idx_getIndex('i',$wlen);
316            foreach($words[$wlen] as $wid => $freq){
317                if($wid<count($index)){
318                    $index[$wid] = idx_updateIndexLine($index[$wid],$pid,$freq);
319                }else{
320                    // New words **should** have been added in increasing order
321                    // starting with the first unassigned index.
322                    // If someone can show how this isn't true, then I'll need to sort
323                    // or do something special.
324                    $index[$wid] = idx_updateIndexLine('',$pid,$freq);
325                }
326                $pagewords[] = "$wlen*$wid";
327            }
328            // save back word index
329            if(!idx_saveIndex('i',$wlen,$index)){
330                trigger_error("Failed to write index", E_USER_ERROR);
331                return false;
332            }
333        }
334    }
335
336    // Remove obsolete index entries
337    $pageword_idx = trim(idx_getIndexLine('pageword','',$pid));
338    if ($pageword_idx !== '') {
339        $oldwords = explode(':',$pageword_idx);
340        $delwords = array_diff($oldwords, $pagewords);
341        $upwords = array();
342        foreach ($delwords as $word) {
343            if($word=='') continue;
344            list($wlen,$wid) = explode('*',$word);
345            $wid = (int)$wid;
346            $upwords[$wlen][] = $wid;
347        }
348        foreach ($upwords as $wlen => $widx) {
349            $index = idx_getIndex('i',$wlen);
350            foreach ($widx as $wid) {
351                $index[$wid] = idx_updateIndexLine($index[$wid],$pid,0);
352            }
353            idx_saveIndex('i',$wlen,$index);
354        }
355    }
356    // Save the reverse index
357    $pageword_idx = join(':',$pagewords)."\n";
358    if(!idx_saveIndexLine('pageword','',$pid,$pageword_idx)){
359        trigger_error("Failed to write word index", E_USER_ERROR);
360        return false;
361    }
362
363    return true;
364}
365
366/**
367 * Write a new index line to the filehandle
368 *
369 * This function writes an line for the index file to the
370 * given filehandle. It removes the given document from
371 * the given line and readds it when $count is >0.
372 *
373 * @deprecated - see idx_updateIndexLine
374 * @author Andreas Gohr <andi@splitbrain.org>
375 */
376function idx_writeIndexLine($fh,$line,$pid,$count){
377    fwrite($fh,idx_updateIndexLine($line,$pid,$count));
378}
379
380/**
381 * Modify an index line with new information
382 *
383 * This returns a line of the index. It removes the
384 * given document from the line and readds it if
385 * $count is >0.
386 *
387 * @author Tom N Harris <tnharris@whoopdedo.org>
388 * @author Andreas Gohr <andi@splitbrain.org>
389 */
390function idx_updateIndexLine($line,$pid,$count){
391    $line = trim($line);
392    $updated = array();
393    if($line != ''){
394        $parts = explode(':',$line);
395        // remove doc from given line
396        foreach($parts as $part){
397            if($part == '') continue;
398            list($doc,$cnt) = explode('*',$part);
399            if($doc != $pid){
400                $updated[] = $part;
401            }
402        }
403    }
404
405    // add doc
406    if ($count){
407        $updated[] = "$pid*$count";
408    }
409
410    return join(':',$updated)."\n";
411}
412
413/**
414 * Get the word lengths that have been indexed.
415 *
416 * Reads the index directory and returns an array of lengths
417 * that there are indices for.
418 *
419 * @author Tom N Harris <tnharris@whoopdedo.org>
420 */
421function idx_indexLengths(&$filter){
422    global $conf;
423    $dir = @opendir($conf['indexdir']);
424    if($dir===false)
425        return array();
426    $idx = array();
427    if(is_array($filter)){
428        while (($f = readdir($dir)) !== false) {
429            if (substr($f,0,1) == 'i' && substr($f,-4) == '.idx'){
430                $i = substr($f,1,-4);
431                if (is_numeric($i) && isset($filter[(int)$i]))
432                    $idx[] = (int)$i;
433            }
434        }
435    }else{
436        // Exact match first.
437        if(@file_exists($conf['indexdir']."/i$filter.idx"))
438            $idx[] = $filter;
439        while (($f = readdir($dir)) !== false) {
440            if (substr($f,0,1) == 'i' && substr($f,-4) == '.idx'){
441                $i = substr($f,1,-4);
442                if (is_numeric($i) && $i > $filter)
443                    $idx[] = (int)$i;
444            }
445        }
446    }
447    closedir($dir);
448    return $idx;
449}
450
451/**
452 * Find the the index number of each search term.
453 *
454 * This will group together words that appear in the same index.
455 * So it should perform better, because it only opens each index once.
456 * Actually, it's not that great. (in my experience) Probably because of the disk cache.
457 * And the sorted function does more work, making it slightly slower in some cases.
458 *
459 * @param array    $words   The query terms. Words should only contain valid characters,
460 *                          with a '*' at either the beginning or end of the word (or both)
461 * @param arrayref $result  Set to word => array("length*id" ...), use this to merge the
462 *                          index locations with the appropriate query term.
463 * @return array            Set to length => array(id ...)
464 *
465 * @author Tom N Harris <tnharris@whoopdedo.org>
466 */
467function idx_getIndexWordsSorted($words,&$result){
468    // parse and sort tokens
469    $tokens = array();
470    $tokenlength = array();
471    $tokenwild = array();
472    foreach($words as $word){
473        $result[$word] = array();
474        $wild = 0;
475        $xword = $word;
476        $wlen = wordlen($word);
477
478        // check for wildcards
479        if(substr($xword,0,1) == '*'){
480            $xword = substr($xword,1);
481            $wild |= 1;
482            $wlen -= 1;
483        }
484        if(substr($xword,-1,1) == '*'){
485            $xword = substr($xword,0,-1);
486            $wild |= 2;
487            $wlen -= 1;
488        }
489        if ($wlen < IDX_MINWORDLENGTH && $wild == 0 && !is_numeric($xword)) continue;
490        if(!isset($tokens[$xword])){
491            $tokenlength[$wlen][] = $xword;
492        }
493        if($wild){
494            $ptn = preg_quote($xword,'/');
495            if(($wild&1) == 0) $ptn = '^'.$ptn;
496            if(($wild&2) == 0) $ptn = $ptn.'$';
497            $tokens[$xword][] = array($word, '/'.$ptn.'/');
498            if(!isset($tokenwild[$xword])) $tokenwild[$xword] = $wlen;
499        }else
500            $tokens[$xword][] = array($word, null);
501    }
502    asort($tokenwild);
503    // $tokens = array( base word => array( [ query word , grep pattern ] ... ) ... )
504    // $tokenlength = array( base word length => base word ... )
505    // $tokenwild = array( base word => base word length ... )
506
507    $length_filter = empty($tokenwild) ? $tokenlength : min(array_keys($tokenlength));
508    $indexes_known = idx_indexLengths($length_filter);
509    if(!empty($tokenwild)) sort($indexes_known);
510    // get word IDs
511    $wids = array();
512    foreach($indexes_known as $ixlen){
513        $word_idx = idx_getIndex('w',$ixlen);
514        // handle exact search
515        if(isset($tokenlength[$ixlen])){
516            foreach($tokenlength[$ixlen] as $xword){
517                $wid = array_search("$xword\n",$word_idx);
518                if(is_int($wid)){
519                    $wids[$ixlen][] = $wid;
520                    foreach($tokens[$xword] as $w)
521                        $result[$w[0]][] = "$ixlen*$wid";
522                }
523            }
524        }
525        // handle wildcard search
526        foreach($tokenwild as $xword => $wlen){
527            if($wlen >= $ixlen) break;
528            foreach($tokens[$xword] as $w){
529                if(is_null($w[1])) continue;
530                foreach(array_keys(preg_grep($w[1],$word_idx)) as $wid){
531                    $wids[$ixlen][] = $wid;
532                    $result[$w[0]][] = "$ixlen*$wid";
533                }
534            }
535        }
536    }
537    return $wids;
538}
539
540/**
541 * Lookup words in index
542 *
543 * Takes an array of word and will return a list of matching
544 * documents for each one.
545 *
546 * Important: No ACL checking is done here! All results are
547 *            returned, regardless of permissions
548 *
549 * @author Andreas Gohr <andi@splitbrain.org>
550 */
551function idx_lookup($words){
552    global $conf;
553
554    $result = array();
555
556    $wids = idx_getIndexWordsSorted($words, $result);
557    if(empty($wids)) return array();
558
559    // load known words and documents
560    $page_idx = idx_getIndex('page','');
561
562    $docs = array();                          // hold docs found
563    foreach(array_keys($wids) as $wlen){
564        $wids[$wlen] = array_unique($wids[$wlen]);
565        $index = idx_getIndex('i',$wlen);
566        foreach($wids[$wlen] as $ixid){
567            if($ixid < count($index))
568                $docs["$wlen*$ixid"] = idx_parseIndexLine($page_idx,$index[$ixid]);
569        }
570    }
571
572    // merge found pages into final result array
573    $final = array();
574    foreach($result as $word => $res){
575        $final[$word] = array();
576        foreach($res as $wid){
577            $hits = &$docs[$wid];
578            foreach ($hits as $hitkey => $hitcnt) {
579                if (!isset($final[$word][$hitkey])) {
580                    $final[$word][$hitkey] = $hitcnt;
581                } else {
582                    $final[$word][$hitkey] += $hitcnt;
583                }
584            }
585        }
586    }
587    return $final;
588}
589
590/**
591 * Returns a list of documents and counts from a index line
592 *
593 * It omits docs with a count of 0 and pages that no longer
594 * exist.
595 *
596 * @param  array  $page_idx The list of known pages
597 * @param  string $line     A line from the main index
598 * @author Andreas Gohr <andi@splitbrain.org>
599 */
600function idx_parseIndexLine(&$page_idx,$line){
601    $result = array();
602
603    $line = trim($line);
604    if($line == '') return $result;
605
606    $parts = explode(':',$line);
607    foreach($parts as $part){
608        if($part == '') continue;
609        list($doc,$cnt) = explode('*',$part);
610        if(!$cnt) continue;
611        $doc = trim($page_idx[$doc]);
612        if(!$doc) continue;
613        // make sure the document still exists
614        if(!page_exists($doc,'',false)) continue;
615
616        $result[$doc] = $cnt;
617    }
618    return $result;
619}
620
621/**
622 * Tokenizes a string into an array of search words
623 *
624 * Uses the same algorithm as idx_getPageWords()
625 *
626 * @param string   $string     the query as given by the user
627 * @param arrayref $stopwords  array of stopwords
628 * @param boolean  $wc         are wildcards allowed?
629 */
630function idx_tokenizer($string,&$stopwords,$wc=false){
631    $words = array();
632    $wc = ($wc) ? '' : $wc = '\*';
633
634    if(preg_match('/[^0-9A-Za-z]/u', $string)){
635        // handle asian chars as single words (may fail on older PHP version)
636        $asia = @preg_replace('/('.IDX_ASIAN.')/u',' \1 ',$string);
637        if(!is_null($asia)) $string = $asia; //recover from regexp failure
638
639        $arr = explode(' ', utf8_stripspecials($string,' ','\._\-:'.$wc));
640        foreach ($arr as $w) {
641            if (!is_numeric($w) && strlen($w) < IDX_MINWORDLENGTH) continue;
642            $w = utf8_strtolower($w);
643            if($stopwords && is_int(array_search("$w\n",$stopwords))) continue;
644            $words[] = $w;
645        }
646    }else{
647        $w = $string;
648        if (!is_numeric($w) && strlen($w) < IDX_MINWORDLENGTH) return $words;
649        $w = strtolower($w);
650        if(is_int(array_search("$w\n",$stopwords))) return $words;
651        $words[] = $w;
652    }
653
654    return $words;
655}
656
657/**
658 * Create a pagewords index from the existing index.
659 *
660 * @author Tom N Harris <tnharris@whoopdedo.org>
661 */
662function idx_upgradePageWords(){
663    global $conf;
664    $page_idx = idx_getIndex('page','');
665    if (empty($page_idx)) return;
666    $pagewords = array();
667    $len = count($page_idx);
668    for ($n=0;$n<$len;$n++){
669        $pagewords[] = array();
670    }
671    unset($page_idx);
672
673    $n=0;
674    foreach (idx_indexLengths($n) as $wlen) {
675        $lines = idx_getIndex('i',$wlen);
676        $len = count($lines);
677        for ($wid=0;$wid<$len;$wid++) {
678            $wkey = "$wlen*$wid";
679            foreach (explode(':',trim($lines[$wid])) as $part) {
680                if($part == '') continue;
681                list($doc,$cnt) = explode('*',$part);
682                $pagewords[(int)$doc][] = $wkey;
683            }
684        }
685    }
686
687    $fn = $conf['indexdir'].'/pageword';
688    $fh = @fopen($fn.'.tmp','w');
689    if (!$fh){
690        trigger_error("Failed to write word index", E_USER_ERROR);
691        return false;
692    }
693    foreach ($pagewords as $line){
694        fwrite($fh, join(':',$line)."\n");
695    }
696    fclose($fh);
697    if($conf['fperm']) chmod($fn.'.tmp', $conf['fperm']);
698    io_rename($fn.'.tmp', $fn.'.idx');
699    return true;
700}
701
702//Setup VIM: ex: et ts=4 enc=utf-8 :
703