LIMA
Libre Multilingual Analyzer — C++ API
Loading...
Searching...
No Matches
FsaAccessBuilderRandom16.cpp
Go to the documentation of this file.
1// Copyright 2002-2013 CEA LIST
2// SPDX-FileCopyrightText: 2022 CEA LIST <gael.de-chalendar@cea.fr>
3//
4// SPDX-License-Identifier: MIT
5
6/***************************************************************************
7 * Copyright (C) 2003 by CEA *
8 * author Olivier MESNARD olivier.mesnard@cea.fr *
9 * *
10 * Compact dictionnary based on finite state automata implemented with *
11 * Boost Graph library. *
12 * Algorithm is described in article from Daciuk, Mihov, Watson & Watson: *
13 * "Incremental Construction of Minimal Acyclic Finite State Automata" *
14 ***************************************************************************/
15
16// From boost library
17#include <boost/config.hpp>
18#include <boost/graph/adjacency_list.hpp>
19
20#include "common/LimaCommon.h"
21#include "common/Data/strwstrtools.h"
22
23#include "FsaAccessBuilderRandom16.h"
24using namespace Lima;
25
26namespace Lima {
27namespace Common {
28namespace FsaAccess {
29
30FsaAccessBuilderRandom16::FsaAccessBuilderRandom16( bool trie_direction_fwd )
31: FsaAccessReader16<selected_graph_types16::builderGraphType>(trie_direction_fwd ) ,
32 m_packingStatus(BUILDER)
33{
34}
35
39
40
41FsaAccessIOHandler<selected_graph_types16::builderGraphType>* FsaAccessBuilderRandom16::getFsaAccessIOHandler() const {
42 return new FsaAccessIOHandlerWithMapping<selected_graph_types16::builderGraphType>();
43// return new FsaAccessIOHandlerWithoutMapping<selected_graph_types16::builderGraphType>();
44}
45
46// Same code as FsaAccessBuilder !!
47// duplicated toi avoid multiple inheritance
48void FsaAccessBuilderRandom16::write( const std::string & filename ){
49
50 std::ofstream os(filename.data(), std::ios::out | std::ios::binary | std::ios::app );
51 if( os.bad() ) {
52 std::string mess = "FsaAccessBuilderRandom16::write: Can't open file " + filename;
53#ifdef DEBUG_CD
54 FSAAIOLOGINIT;
55 LERROR;
56#endif
57 throw( FsaNotSaved( mess ) );
58 }
59// os.seekp(HEADER_SIZE ,std::ios_base::beg );
60 FsaAccessBuilderRandom16::write( os );
61}
62
63
64// Same code as FsaAccessBuilderRandom !!
65// duplicated toi avoid multiple inheritance
66void FsaAccessBuilderRandom16::write ( std::ostream &os ){
67#ifdef DEBUG_CD
68 FSAAIOLOGINIT;
69 LDEBUG << "FsaAccessBuilderRandom16::write(std::ostream)";
70#endif
71
72 FsaAccessOStreamWrapper ow(os);
73 FsaAccessBuilderRandom16::write(ow);
74}
75
76// Same code as FsaAccessBuilderRandom !!
77// duplicated toi avoid multiple inheritance
78void FsaAccessBuilderRandom16::write ( FsaAccessDataOutputHandler& oh ){
79#ifdef DEBUG_CD
80 FSAAIOLOGINIT;
81 LDEBUG << "FsaAccessBuilderRandom16::write(std::ostream)";
82#endif
83
84 FsaAccessOutputHandlerWrapper ow(oh);
85 FsaAccessBuilderRandom16::write(ow);
86}
87
88// Same code as FsaAccessBuilder !!
89// duplicated toi avoid multiple inheritance
90void FsaAccessBuilderRandom16::write( AbstractFsaAccessOStreamWrapper &ow ){
91#ifdef DEBUG_CD
92 FSAAIOLOGINIT;
93 LDEBUG << "FsaAccessBuilderRandom16::write()";
94#endif
95
96 FsaAccessHeader::setPackingStatus(m_packingStatus);
97
98 boost::graph_traits<graphType>::vertices_size_type nbVerts =
99 boost::num_vertices(m_graph);
100 boost::graph_traits<graphType>::edges_size_type nbEdges =
101 boost::num_edges(m_graph);
102
103 FsaAccessHeader::setNbVertices(nbVerts);
104 FsaAccessHeader::setNbEdges(nbEdges);
105
106 FsaAccessHeader::write(ow);
107
108 writeBody( ow );
109}
110
111void FsaAccessBuilderRandom16::addRandomWord( const LimaString & newWord ) {
112 FSAALOGINIT;
113#ifdef DEBUG_CD
114 LDEBUG << "FsaAccessBuilderRandom16::addRandomWord("
115 << newWord << ")";
116 std::ostringstream stro1(std::ios::in | std::ios::out);
117 stro1 << Lima::Common::Misc::limastring2utf8stdstring(LimaString(newWord.data()))
118 << "), m_rootVertex=" << m_rootVertex;
119 LWARN << "FsaAccessBuilderRandom16::addRandomWord("
120 << stro1.str().c_str();
121
122#endif
123
124 PrefixIterator* prefixIt = getPrefixIterator(newWord);
125 dicoVertex root = m_rootVertex;
126// checkIntegrity( m_rootVertex );
127 getPrefix( root, prefixIt );
128 dicoGraph_traits16<graphType>::nconst_vname_map_type vname_map =
129 boost::get(boost::vertex_name,m_graph);
130
131 dicoVertex prefix_leaf;
132
133 if( !prefixIt->hasNextLetter() ) {
134 delete prefixIt;
135 std::pair<AccessSuperWordIterator, AccessSuperWordIterator> superwords = getSuperWords(newWord );
136 if( superwords.first == superwords.second ) {
137 LWARN << "FsaAccessBuilderRandom16::addRandomWord: "
138 << newWord
139 << " already in dictionary!!";
140 return;
141 }
142#ifdef DEBUG_CD
143 LDEBUG << "FsaAccessBuilderRandom16::addRandomWord: "
144 << newWord
145 << " as prefix of existing word";
146#endif
147 Lima::LimaString superword =
148 *(superwords.first);
149 (superwords.first)++;
150 for( ; superwords.first != superwords.second ; (superwords.first)++ ) {
151 Lima::LimaString nextSuperword =
152 *(superwords.first);
153 if( nextSuperword.length() <= superword.length() )
154 break;
155 else
156 superword = nextSuperword;
157 }
158#ifdef DEBUG_CD
159 LDEBUG << "FsaAccessBuilderRandom16::addRandomWord: superWord = "
160 << superword;
161#endif
162
163 PrefixIterator* prefixItSuperWord = getPrefixIterator(superword);
164 /*bool hasFirstState =*/ scanAndCloneConfluentStates( m_rootVertex, prefixItSuperWord, prefix_leaf );
165
166 PrefixIterator* prefixItWord = getPrefixIterator(newWord);
167 dicoVertex root = m_rootVertex;
168 getPrefix( root, prefixItWord );
169#ifdef DEBUG_CD
170 LWARN << "FsaAccessBuilderRandom16::addRandomWord: put(vname_map,"
171 << root << "," << get(vname_map, root)
172 << " -> ";
173#endif
174 put(vname_map, root, get(vname_map, root)|FINAL_16);
175#ifdef DEBUG_CD
176 LWARN << get(vname_map, root) << ")";
177#endif
178#ifdef DEBUG_CD
179 LWARN << "FsaAccessBuilderRandom16::addRandomWord: put(vname_map,"
180 << prefix_leaf << "," << get(vname_map, prefix_leaf)
181 << " -> ";
182#endif
183 put(vname_map, prefix_leaf, get(vname_map, prefix_leaf)|FINAL_16);
184#ifdef DEBUG_CD
185 LWARN << get(vname_map, prefix_leaf) << ")";
186#endif
187
188 prefixItSuperWord = getPrefixIterator(superword);
189 replaceOrRegister( m_rootVertex, prefixItSuperWord );
190 delete prefixItSuperWord;
191
192 prefixItWord = getPrefixIterator(newWord);
193 std::ostringstream stro (std::ios::in | std::ios::out);
194 stro << m_rootVertex << "," << *prefixItWord;
195#ifdef DEBUG_CD
196 LDEBUG << "FsaAccessBuilderRandom16::addRandomWord: updateHash("
197 << stro.str().c_str() << ")";
198#endif
199 updateHash( m_rootVertex, prefixItWord );
200 delete prefixItWord;
201
202// checkIntegrity( m_rootVertex );
203 return;
204 }
205
206 if( prefixIt->getWordPos() == 0 ) {
207#ifdef DEBUG_CD
208 LDEBUG << "FsaAccessBuilderRandom16::addRandomWord: add complete word to root ";
209#endif
210 prefix_leaf = m_rootVertex;
211 }
212 else {
213 const LimaString prefix = prefixIt->getPastPrefix();
214 PrefixIterator* prefixItClone = getPrefixIterator(prefix);
215#ifdef DEBUG_CD
216 LDEBUG << "FsaAccessBuilderRandom16::addRandomWord: m_rootVertex=" << m_rootVertex;
217#endif
218 /*bool hasFirstState =*/ scanAndCloneConfluentStates( m_rootVertex, prefixItClone, prefix_leaf );
219// checkIntegrity( prefix_leaf );
220
221#ifdef DEBUG_CD
222// LDEBUG << "FsaAccessBuilderRandom16::addRandomWord: addSuffix " << prefix->getCurrentPrefix() << " to " << prefix_leaf;
223 LDEBUG << "FsaAccessBuilderRandom16::addRandomWord: addSuffix to " << prefix_leaf;
224#endif
225 }
226 if( prefixIt->hasNextLetter() ) {
227 // ad first transition of suffix
228 dicoVertex newState = add_vertex(m_graph);
229 put(vname_map, newState, 0);
230
231 int32_t wordOffset;
232 char32_t currentChar = prefixIt->getNextLetter(wordOffset);
233
234#ifdef DEBUG_CD
235 LDEBUG << "FsaAccessBuilderRandom16::addRandomWord: add first letter of suffix "
236 << currentChar;
237#endif
238// checkIntegrity( prefix_leaf );
239 addEdge( prefix_leaf, newState, currentChar, prefixIt->getCurrentContent(), wordOffset );
240// checkIntegrity( prefix_leaf );
241 prefixIt->next(wordOffset);
242
243 const LimaString trail = prefixIt->getCurrentPrefix();
244 PrefixIterator* prefixItAdd = getPrefixIterator(trail);
245// PrefixIterator* prefixItAdd = getPrefixIterator(prefixIt->getCurrentPrefix());
246 if( prefixItAdd->hasNextLetter() ) {
247#ifdef DEBUG_CD
248// LDEBUG << "FsaAccessBuilderRandom16::addRandomWord: add end of suffix " << trail
249 LDEBUG << "FsaAccessBuilderRandom16::addRandomWord: add end of suffix "
250 << " to " << newState;
251#endif
252 addSuffix( newState, prefixItAdd);
253 }
254 else {
255 put(vname_map, newState, FINAL_16);
256 }
257 PrefixIterator* prefixItWord = getPrefixIterator(newWord);
258 replaceOrRegister( m_rootVertex, prefixItWord );
259 delete prefixItWord;
260
261 prefixItWord = getPrefixIterator(newWord);
262 updateHash( m_rootVertex, prefixItWord );
263 delete prefixItWord;
264 }
265// checkIntegrity( prefix_leaf );
266
267// checkIntegrity( m_rootVertex );
268
269 return;
270
271}
272
283bool FsaAccessBuilderRandom16::scanAndCloneConfluentStates(
284 boost::graph_traits<graphType>::vertex_descriptor from,
285 PrefixIterator* prefixIt,
286 boost::graph_traits<graphType>::vertex_descriptor& lastState ) {
287#ifdef DEBUG_CD
288 FSAALOGINIT;
289 LDEBUG << "FsaAccessBuilderRandom16::scanAndCloneConfluentStates("
290 << from << "," << prefixIt->getCurrentPrefix() << ")";
291#endif
292 dicoGraph_traits16<graphType>::nconst_vtext_map_type vtext_map =
293 boost::get(vertex_text,m_graph);
294 dicoGraph_traits16<graphType>::nconst_vname_map_type vname_map =
295 boost::get(boost::vertex_name,m_graph);
296 dicoGraph_traits16<graphType>::nconst_vcount_map_type vcount_map =
297 boost::get(vertex_count,m_graph);
298
299 int32_t wordOffset;
300 for( ; prefixIt->hasNextLetter() ; ) {
301 // get first char (or last one if reverse) of word to search for in graph
302 char32_t currentChar = prefixIt->getNextLetter(wordOffset);
303#ifdef DEBUG_CD
304 LDEBUG << "FsaAccessBuilderRandom16::scanAndCloneConfluentStates: currentChar="
305 << currentChar << ")";
306#endif
307/* TODO: replace FsaAccess16<graphType>::findEdge() by ForwardPrefixIterator::findEdge()
308
309 Lima::LimaString& text = get(vtext_map,from);
310 int32_t highCharTextPos = get(vname_map,from)&TEXT_POS_16;
311 ForwardPrefixIterator vertexTextIt( text );
312 int32_t edgeOffset = vertexTextIt.findEdge( currentChar, wordOffset, highCharTextPos);
313*/
314 // find the path in the atomaton defined by the prefix
315 int32_t edgeOffset = 0;
316 int32_t textOffset = 0;
317 Lima::LimaString& text = get(vtext_map,from);
318#ifdef DEBUG_CD
319 std::string text8 = Lima::Common::Misc::limastring2utf8stdstring(LimaString(text.data()));
320 LDEBUG << "FsaAccessBuilderRandom16::scanAndCloneConfluentStates: text = " << text8.c_str();
321#endif
322 int32_t highCharTextPos = get(vname_map,from)&TEXT_POS_16;
323 if( wordOffset == 1 ) {
324 textOffset = findEdge( currentChar, text, 0, highCharTextPos, wordOffset );
325 edgeOffset = textOffset;
326 }
327 else {
328 textOffset = findEdge( currentChar, text, highCharTextPos, text.length(), wordOffset );
329 edgeOffset = highCharTextPos + (textOffset - highCharTextPos)/2;
330 }
331
332 if( edgeOffset >= 0 ) {
333 boost::graph_traits<graphType>::out_edge_iterator ei, edge_end;
334 boost::tie(ei,edge_end) = boost::out_edges(from,m_graph);
335
336// TODO: optimize it!
337// edgeOffset = 0;
338// dicoEdgeType edge = *(ei+edgeOffset);
339 for( int i = 0 ; i < edgeOffset ; i++ )
340 ei++;
341 dicoEdgeType edge = *ei;
342
343 boost::graph_traits<graphType>::vertex_descriptor to = target(edge, m_graph);
344#ifdef DEBUG_CD
345 LDEBUG << "FsaAccessBuilderRandom16::scanAndCloneConfluentStates: match " << edgeOffset;
346#endif
347 graphType::degree_size_type ind = boost::in_degree(to, m_graph);
348 if( ind > 1 ) {
349 // c'est un etat confluent: suppressEdge( from, to, currentChar );
350 // remove element from vector counts
351 // tableau des coefficients
352 graphType::degree_size_type outd0 = boost::out_degree(from, m_graph);
353 std::vector<int>& counts = get(vcount_map,from);
354 if( outd0 > 1 ) {
355 Q_ASSERT( (counts.size() + 1) == outd0 );
356 counts.pop_back();
357 Q_ASSERT( (counts.size() + 2) == outd0 );
358 }
359 else {
360 Q_ASSERT( counts.size() == 0 );
361 }
362
363#ifdef DEBUG_CD
364 LDEBUG << "FsaAccessBuilderRandom16::scanAndCloneConfluentStates: before remove_edge("
365 << from << "," << to << "), outd=" << outd0;
366 std::ostringstream oss2;
367 oss2 << "FsaAccessBuilderRandom16::scanAndCloneConfluentStates: remove_edge("
368 << edge << "," << (int)currentChar << ")";
369 LDEBUG << oss2.str().c_str();
370#endif
371 remove_edge(edge, m_graph);
372 graphType::degree_size_type outd = boost::out_degree(from, m_graph);
373#ifdef DEBUG_CD
374 LDEBUG << "FsaAccessBuilderRandom16::scanAndCloneConfluentStates: after remove_edge, outd="
375 << outd;
376#endif
377 Q_ASSERT( (outd+1) == outd0);
378 if( outd > 1 )
379 Q_ASSERT( (counts.size() +1) == outd);
380 else
381 Q_ASSERT( counts.size() == 0 );
382
383#ifdef DEBUG_CD
384 LDEBUG << "FsaAccessBuilderRandom16::scanAndCloneConfluentStates: before erase text[to] ="
385 << LimaString(text.data());
386#endif
387 text.remove(textOffset, wordOffset);
388 Q_ASSERT( static_cast<graphType::degree_size_type>(text.size()) == outd);
389#ifdef DEBUG_CD
390 LDEBUG << "FsaAccessBuilderRandom16::scanAndCloneConfluentStates: after erase text[to] ="
391 << LimaString(text.data());
392#endif
393 VERTEX_PROPERTY_16 vval = get(vname_map, from);
394#ifdef DEBUG_CD
395 LDEBUG << "FsaAccessBuilderRandom16::scanAndCloneConfluentStates: read val[to] ="
396 << vval;
397#endif
398 VERTEX_PROPERTY_16 qualif = vval & QUALITY_16;
399 VERTEX_PROPERTY_16 hicharOff = vval & TEXT_POS_16;
400 if( wordOffset == 1 )
401 hicharOff--;
402 Q_ASSERT( hicharOff == outd);
403#ifdef DEBUG_CD
404 LDEBUG << "FsaAccessBuilderRandom16::scanAndCloneConfluentStates: set val[to] :="
405 << ( (qualif&(~HEAD_OF_CLASS_16)) | hicharOff);
406#endif
407 put(vname_map, from, (qualif&(~HEAD_OF_CLASS_16)) | hicharOff);
408
409 boost::graph_traits<graphType>::vertex_descriptor newState;
410// bool LIMA_UNUSED(ret) = cloneConfluentStates(currentChar, to, word_content, wordPos, wordOffset, prefix_length, from, newState);
411 /*bool ret =*/ cloneConfluentStates(currentChar, wordOffset, to, prefixIt, from, newState);
412
413#ifdef DEBUG_CD
414 LDEBUG << "FsaAccessBuilderRandom16::scanAndCloneConfluentStates: duplicate out edges of "
415 << to << " into " << newState;
416#endif
417 lastState = newState;
418 break;
419 }
420 else {
421 prefixIt->next(wordOffset);
422 from = to;
423 lastState = to;
424 }
425 }
426 else {
427#ifdef DEBUG_CD
428 LWARN << "FsaAccessBuilderRandom16::scanAndCloneConfluentStates: no match for ";
429#endif
430 return false;
431 }
432 }
433 return true;
434}
435
455bool FsaAccessBuilderRandom16::cloneConfluentStates(
456 char32_t currentChar,
457 int32_t wordOffset,
458 boost::graph_traits<graphType>::vertex_descriptor& toOldPath,
459 PrefixIterator* prefixIt,
460 boost::graph_traits<graphType>::vertex_descriptor fromNewPath,
461 boost::graph_traits<graphType>::vertex_descriptor& toNewPath ) {
462
463#ifdef DEBUG_CD
464 FSAALOGINIT;
465 LDEBUG << "FsaAccessBuilderRandom16::cloneConfluentStates("
466 << toOldPath << "," << prefixIt->getCurrentPrefix()
467 << "," << wordOffset
468 << "," << fromNewPath << ")";
469#endif
470 dicoGraph_traits16<graphType>::nconst_vtext_map_type vtext_map =
471 boost::get(vertex_text,m_graph);
472 dicoGraph_traits16<graphType>::nconst_vname_map_type vname_map =
473 boost::get(boost::vertex_name,m_graph);
474
475#ifdef DEBUG_CD
476 graphType::degree_size_type out_size = boost::out_degree(fromNewPath, m_graph);
477 LDEBUG << "FsaAccessBuilderRandom16::cloneConfluentStates: degree_size_type("
478 << fromNewPath << ")=" << out_size << ")";
479#endif
480 // Create a new state
481 toNewPath = add_vertex(m_graph);
482 // put(vname_map, toNewPath, 0);
483 // put(vtext_map, newState, Lima::LimaString());
484 //put(vcount_map, newState, std::vector<int>());
485
486 addEdge(fromNewPath, toNewPath, currentChar, prefixIt->getCurrentContent(), wordOffset );
487 cloneVertex(toOldPath, toNewPath );
488
489 prefixIt->next(wordOffset);
490
491 // get first char (or last one if reverse) of word to search for in graph
492 if( !prefixIt->hasNextLetter() ) {
493 return true;
494 }
495 currentChar = prefixIt->getNextLetter(wordOffset);
496
497 // find the path in the atomaton defined by the prefix
498 int32_t edgeOffset = 0;
499 // iterator to select the right path among the out_edges
500 boost::graph_traits<graphType>::out_edge_iterator ei, edge_end;
501 boost::tie(ei,edge_end) = boost::out_edges(toOldPath, m_graph);
502 const Lima::LimaString& text = get(vtext_map,toOldPath);
503 int32_t highCharTextPos = get(vname_map,toOldPath)&TEXT_POS_16;
504 if( wordOffset == 1 ) {
505 edgeOffset = findEdge( currentChar, text, 0, highCharTextPos, wordOffset );
506 }
507 else {
508 int32_t textOffset;
509 textOffset = findEdge( currentChar, text, highCharTextPos, text.length(), wordOffset );
510 edgeOffset = highCharTextPos + (textOffset - highCharTextPos)/2;
511 }
512
513 if( edgeOffset >= 0 ) {
514 boost::graph_traits<graphType>::out_edge_iterator ei, edge_end;
515 boost::tie(ei,edge_end) = boost::out_edges(toOldPath,m_graph);
516 dicoEdgeType edge = *(ei+edgeOffset);
517
518#ifdef DEBUG_CD
519 LDEBUG << "FsaAccessBuilderRandom16::cloneConfluentStates: match " << edgeOffset;
520#endif
521 dicoVertex oldTarget = target(edge, m_graph);
522
523 suppressEdge(toNewPath, oldTarget, currentChar, prefixIt->getCurrentContent(), wordOffset);
524 toOldPath = oldTarget;
525
526 bool ret = cloneConfluentStates( currentChar, wordOffset, toOldPath,
527 prefixIt, toNewPath, toNewPath);
528 return ret;
529 }
530 else {
531#ifdef DEBUG_CD
532 LERROR << "FsaAccessBuilderRandom16::cloneConfluentStates: no match for"
533 << currentChar;
534#endif
535 return false;
536 }
537}
538
539// creation du clone d'un noeud: duplique les transitions depuis ce noeud
540void FsaAccessBuilderRandom16::cloneVertex(
541 const boost::graph_traits<graphType>::vertex_descriptor oldTo,
542 const boost::graph_traits<graphType>::vertex_descriptor newTo )
543{
544#ifdef DEBUG_CD
545 FSAALOGINIT;
546 LDEBUG << "FsaAccessBuilderRandom16::cloneVertex("
547 << oldTo << ", " << newTo << ")";
548#endif
549 dicoGraph_traits16<graphType>::nconst_vtext_map_type vtext_map =
550 boost::get(vertex_text,m_graph);
551 dicoGraph_traits16<graphType>::nconst_vname_map_type vname_map =
552 boost::get(boost::vertex_name,m_graph);
553 dicoGraph_traits16<graphType>::nconst_vcount_map_type vcount_map =
554 boost::get(vertex_count,m_graph);
555
556 boost::graph_traits<graphType>::out_edge_iterator ei, edge_end;
557 boost::tie(ei,edge_end) = boost::out_edges(oldTo, m_graph);
558 graphType::degree_size_type outd0 = boost::out_degree(newTo, m_graph);
559 graphType::degree_size_type outdRef = boost::out_degree(oldTo, m_graph);
560 Q_ASSERT(outd0 == 0);
561 for( ; ei != edge_end ; ei++ ) {
562 dicoVertex currentTarget = target(*ei,m_graph);
563#ifdef DEBUG_CD
564 LDEBUG << "FsaAccessBuilderRandom16::cloneVertex: add_edge("
565 << newTo << "," << currentTarget << ")";
566#endif
567 add_edge(newTo, currentTarget, m_graph );
568 }
569 graphType::degree_size_type outd = boost::out_degree(newTo, m_graph);
570 Q_ASSERT( outd == outdRef );
571 // std::vector<int>& counts = get(vcount_map,oldTo);
572 std::vector<int>& counts = get(vcount_map,oldTo);
573 put(vcount_map,newTo,counts);
574 put(vtext_map,newTo,get(vtext_map,oldTo));
575
576 std::vector<int>& newCounts = get(vcount_map,newTo);
577 if( outd > 1 )
578 Q_ASSERT( (newCounts.size()+1) == outd );
579 else
580 Q_ASSERT( newCounts.size() == 0 );
581
582 Lima::LimaString& text = get(vtext_map,newTo);
583 Q_ASSERT( static_cast<graphType::degree_size_type>(text.size()) == outd );
584
585 // mise a jour du nombre de caracteres avec remise a zero des caracteres HEAD_OF_CLASS_16 et SET_16
586 VERTEX_PROPERTY_16 vval = get(vname_map, oldTo);
587 vval &= (~(HEAD_OF_CLASS_16 | SET_16));
588 put(vname_map,newTo,vval);
589 Q_ASSERT( (get(vname_map, newTo)&TEXT_POS_16) == outd );
590}
591
592// Insertion d'une transition supplementaire a partir du noeud from.
593// Attention: pour respecter le meme ordre pour le tableau des caracteres qui constituent
594// les etiquettes des transitions et pour le (tableau?) des transition, il faut
595// Repliquer le tableau des transitions en sortie de from pour
596// controler leur ordre (le conteneur n'est pas trie)
597void FsaAccessBuilderRandom16::addEdge(
598 const boost::graph_traits<graphType>::vertex_descriptor from,
599 const boost::graph_traits<graphType>::vertex_descriptor to,
600 const char32_t currentChar,
601 const Lima::LimaChar* const word_content,
602 const int32_t wordOffset ) {
603
604#ifdef DEBUG_CD
605 FSAALOGINIT;
606 LDEBUG << "FsaAccessBuilderRandom16::addEdge("
607 << from << ", " << to << ", " << currentChar << ","
608 << LimaString(*word_content) << ", " << wordOffset << ")";
609#endif
610 dicoGraph_traits16<graphType>::nconst_vtext_map_type vtext_map =
611 boost::get(vertex_text,m_graph);
612 dicoGraph_traits16<graphType>::nconst_vname_map_type vname_map =
613 boost::get(boost::vertex_name,m_graph);
614 dicoGraph_traits16<graphType>::nconst_vcount_map_type vcount_map =
615 boost::get(vertex_count,m_graph);
616
617 Lima::LimaString& text = get(vtext_map,from);
618 VERTEX_PROPERTY_16 vval = get(vname_map, from);
619 VERTEX_PROPERTY_16 qualif = vval & QUALITY_16;
620 VERTEX_PROPERTY_16 highCharTextPos = vval & TEXT_POS_16;
621#ifdef DEBUG_CD
622 LDEBUG << "FsaAccessBuilderRandom16::addEdge: vval="
623 << vval
624 << ", highCharTextPos=" << highCharTextPos ;
625#endif
626
627 // tableau des coefficients
628 std::vector<int>& counts = get(vcount_map,from);
629 graphType::degree_size_type outd0 = boost::out_degree(from, m_graph);
630
631 int32_t textOffset0;
632 if( wordOffset == 1 ) {
633 if( highCharTextPos > 0 )
634 textOffset0 = findOffsetToInsertBefore( currentChar, text, 0, highCharTextPos, wordOffset );
635 else
636 textOffset0 = 0;
637
638 // Memorisation des transitions au dela de textOffset
639 std::list<dicoVertex> newOrderedTargetList;
640
641 // degree_size_type size = out_degree(from, m_graph);
642 // iterator to duplicate the list of out_edges
643 boost::graph_traits<graphType>::out_edge_iterator ei, edge_end;
644 boost::tie(ei,edge_end) = boost::out_edges(from,m_graph);
645 int32_t textOffset(0);
646 // fill the list up to the new transition to be created
647 for( ; ei != edge_end ; ei++ ) {
648 if( textOffset == textOffset0 )
649 break;
650#ifdef DEBUG_CD
651// LDEBUG << "FsaAccessBuilderRandom16::addEdge: newOrderedTargetList.push_back("
652// << (*ei) << ") (1)";
653#endif
654 newOrderedTargetList.push_back(target(*ei,m_graph));
655 textOffset++;
656 }
657
658 // add target of new transition
659 newOrderedTargetList.push_back(to);
660 // fill the end of the list
661 for( ; ei != edge_end ; ei++ ) {
662#ifdef DEBUG_CD
663// LDEBUG << "FsaAccessBuilderRandom16::addEdge: newOrderedTargetList.push_back("
664// << (*ei) << ") (2)";
665#endif
666 newOrderedTargetList.push_back(target(*ei,m_graph));
667 }
668 // remove all out_edges
669#ifdef DEBUG_CD
670 LDEBUG << "FsaAccessBuilderRandom16::addEdge: clear_edge("
671 << from << ")" << "(" << newOrderedTargetList.size() << ")";
672#endif
673 clear_out_edges(from, m_graph);
674 Q_ASSERT(boost::out_degree(from, m_graph) == 0);
675 // add new list of out_edges
676 for( std::list<dicoVertex>::const_iterator vIt = newOrderedTargetList.begin() ;
677 vIt != newOrderedTargetList.end() ; vIt++ ) {
678#ifdef DEBUG_CD
679 LDEBUG << "FsaAccessBuilderRandom16::addEdge: add_edge("
680 << from << "," << *vIt << "";
681#endif
682 add_edge(from, *vIt, m_graph );
683 }
684 graphType::degree_size_type outd = boost::out_degree(from, m_graph);
685 Q_ASSERT(outd == newOrderedTargetList.size() );
686 Q_ASSERT(outd == (outd0+1) );
687 // insert an additional element with value 0 for vector counts
688 // value will be set later within updateHash() function
689 if (outd > 1 ) {
690#ifdef DEBUG_CD
691 LDEBUG << "FsaAccessBuilderRandom16::addEdge: counts.push_back(0)";
692#endif
693 counts.push_back(0);
694 }
695 // adjust highCharTextPos
696 highCharTextPos++;
697#ifdef DEBUG_CD
698 LDEBUG << "FsaAccessBuilderRandom16::addEdge: outd=" << outd
699 << ", highCharTextPos = " << highCharTextPos;
700#endif
701 Q_ASSERT(outd == highCharTextPos );
702 // from has been modified
703 // set vertex "from" as possibly no more "head of class"
704 qualif = qualif & (~HEAD_OF_CLASS_16);
705#ifdef DEBUG_CD
706 LDEBUG << "FsaAccessBuilderRandom16::addEdge: put(vname_map,"
707 << from << "," << qualif
708 << " | " << highCharTextPos << "" ;
709#endif
710 put(vname_map, from, qualif | highCharTextPos);
711#ifdef DEBUG_CD
712 LDEBUG << "FsaAccessBuilderRandom16::addEdge: text("
713 << from << ")="
714 << LimaString(get(vtext_map,from).data())
715 ;
716 LDEBUG << "FsaAccessBuilderRandom16::addEdge: text="
717 << LimaString(text.data())
718 ;
719 Lima::LimaString textpart = LimaString(word_content).left(wordOffset);
720 LDEBUG << "FsaAccessBuilderRandom16::addEdge: text.insert("
721 << textOffset0 << ","
722 << LimaString(textpart.data()) << ")";
723#endif
724 text.insert(textOffset0, word_content, wordOffset);
725#ifdef DEBUG_CD
726 LDEBUG << "FsaAccessBuilderRandom16::addEdge: text("
727 << from << ")="
728 << LimaString(get(vtext_map,from).data())
729 ;
730 LDEBUG << "FsaAccessBuilderRandom16::addEdge: text="
731 << LimaString(text.data());
732#endif
733 }
734 else {
735#ifdef DEBUG_CD
736 LDEBUG << "FsaAccessBuilderRandom16::addEdge: findOffsetToInsertBefore("
737 << currentChar << ","
738 << LimaString(text.data())
739 << ")";
740#endif
741 textOffset0 = findOffsetToInsertBefore( currentChar, text, highCharTextPos, text.length(), wordOffset );
742 Q_ASSERT(false);
743 // TODO:
744 }
745
746 graphType::degree_size_type outdCheck = boost::out_degree(from, m_graph);
747 if( outdCheck > 1 )
748 Q_ASSERT( (counts.size()+1) == outdCheck );
749 else
750 Q_ASSERT( counts.size() == 0 );
751 Q_ASSERT( (get(vname_map, from)&TEXT_POS_16) == outdCheck );
752 Lima::LimaString& textCheck = get(vtext_map,from);
753 Q_ASSERT( static_cast<graphType::degree_size_type>(textCheck.size()) == outdCheck );
754}
755
756// Remplacement d'une transition a partir du noeud from. Utile pour la fonction merge
757// Attention: pour respecter le meme ordre pour le tableau des caracteres qui constituent
758// les etiquettes des transitions et pour le (tableau?) des transition, il faut
759// Repliquer le tableau des transitions en sortie de from pour
760// controler leur ordre (le conteneur n'est pas trie)
761// par contre, contrairement a addEdge on considere que les proprietes (et en particulier
762// le tableau de caractere) ne changent pas
763void FsaAccessBuilderRandom16::replaceEdge(
764 const boost::graph_traits<graphType>::vertex_descriptor from,
765 const boost::graph_traits<graphType>::vertex_descriptor to,
766 const char32_t currentChar,
767 const int32_t wordOffset ) {
768
769#ifdef DEBUG_CD
770 FSAALOGINIT;
771 LDEBUG << "FsaAccessBuilderRandom16::replaceEdge("
772 << from << ", " << to << ", " << currentChar << ","
773 << ", " << wordOffset << ")";
774#endif
775 dicoGraph_traits16<graphType>::nconst_vtext_map_type vtext_map =
776 boost::get(vertex_text,m_graph);
777 dicoGraph_traits16<graphType>::nconst_vcount_map_type vcount_map =
778 boost::get(vertex_count,m_graph);
779 dicoGraph_traits16<graphType>::nconst_vname_map_type vname_map =
780 boost::get(boost::vertex_name,m_graph);
781
782 Lima::LimaString& text = get(vtext_map,from);
783
784 VERTEX_PROPERTY_16 vval = get(vname_map, from);
785 VERTEX_PROPERTY_16 qualif = vval & QUALITY_16;
786 VERTEX_PROPERTY_16 highCharTextPos = vval & TEXT_POS_16;
787
788 graphType::degree_size_type outd0 = boost::out_degree(from, m_graph);
789 uint32_t textOffset0;
790 if( wordOffset == 1 ) {
791 if( highCharTextPos > 0 )
792 textOffset0 = findOffsetToInsertBefore( currentChar, text, 0, highCharTextPos, wordOffset );
793 else
794 textOffset0 = 0;
795
796#ifdef DEBUG_CD
797 LDEBUG << "FsaAccessBuilderRandom16::replaceEdge: textOffset0="
798 << textOffset0;
799#endif
800
801 // Memorisation des transitions au dela de textOffset
802 std::list<dicoVertex> newOrderedTargetList;
803
804 // degree_size_type size = out_degree(from, m_graph);
805 // iterator to duplicate the list of out_edges
806 boost::graph_traits<graphType>::out_edge_iterator ei, edge_end;
807 boost::tie(ei,edge_end) = boost::out_edges(from,m_graph);
808 uint32_t textOffset(0);
809 // fill the list up to the new transition to be created
810 for( ; ei != edge_end ; ei++ ) {
811 if( textOffset == textOffset0 ) {
812 ei++;
813 break;
814 }
815#ifdef DEBUG_CD
816// LDEBUG << "FsaAccessBuilderRandom16::replaceEdge: newOrderedTargetList.push_back("
817// << (*ei).c_str() << ") (1)";
818#endif
819 newOrderedTargetList.push_back(target(*ei,m_graph));
820 textOffset++;
821 }
822 newOrderedTargetList.push_back(to);
823 Q_ASSERT(newOrderedTargetList.size() == textOffset+1);
824
825 // fill the end of the list
826 for( ; ei != edge_end ; ei++ ) {
827#ifdef DEBUG_CD
828// LDEBUG << "FsaAccessBuilderRandom16::replaceEdge: newOrderedTargetList.push_back("
829// << *ei << ") (2)";
830#endif
831 newOrderedTargetList.push_back(target(*ei,m_graph));
832 }
833 Q_ASSERT(newOrderedTargetList.size() == outd0);
834 // remove all out_edges
835#ifdef DEBUG_CD
836 LDEBUG << "FsaAccessBuilderRandom16::replaceEdge: clear_edge("
837 << from << ")";
838#endif
839 clear_out_edges(from, m_graph);
840 Q_ASSERT(boost::out_degree(from, m_graph) == 0);
841 // add new list of out_edges
842 for( std::list<dicoVertex>::iterator vIt = newOrderedTargetList.begin() ;
843 vIt != newOrderedTargetList.end() ; vIt++ ) {
844#ifdef DEBUG_CD
845 LDEBUG << "FsaAccessBuilderRandom16::replaceEdge: add_edge("
846 << from << "," << *vIt << "";
847#endif
848 add_edge(from, *vIt, m_graph );
849 }
850 Q_ASSERT(boost::out_degree(from, m_graph) == outd0);
851 // from has been modified
852 // set vertex "from" as possibly no more "head of class"
853 qualif = qualif & (~HEAD_OF_CLASS_16);
854#ifdef DEBUG_CD
855 LDEBUG << "FsaAccessBuilderRandom16::replaceEdge: put(vname_map,"
856 << from << "," << qualif << " | " << highCharTextPos << "";
857#endif
858 put(vname_map, from, qualif | highCharTextPos);
859 }
860 else {
861#ifdef DEBUG_CD
862 LDEBUG << "FsaAccessBuilderRandom16::replaceEdge: findOffsetToInsertBefore("
863// << currentChar << "," << text << ")";
864 << currentChar << "," << ")";
865#endif
866 textOffset0 = findOffsetToInsertBefore( currentChar, text, highCharTextPos, text.length(), wordOffset );
867 // TODO:
868 Q_ASSERT(false);
869 }
870
871 // check
872 Q_ASSERT( (get(vname_map, from)&TEXT_POS_16) == outd0 );
873 std::vector<int>& counts = get(vcount_map,from);
874 if( outd0 > 1 )
875 Q_ASSERT( (counts.size()+1) == outd0 );
876 else
877 Q_ASSERT( counts.size() == 0 );
878 Lima::LimaString& textCheck = get(vtext_map,from);
879 Q_ASSERT( static_cast<graphType::degree_size_type>(textCheck.size()) == outd0 );
880
881}
882
883// suppression d'une transition avec une etiquette precise entre deux noueds
884void FsaAccessBuilderRandom16::suppressEdge(
885 const boost::graph_traits<graphType>::vertex_descriptor from,
886 const boost::graph_traits<graphType>::vertex_descriptor to,
887 const char32_t currentChar,
888 const Lima::LimaChar* const word_content,
889 const int32_t wordOffset ) {
890
891#ifdef DEBUG_CD
892 FSAALOGINIT;
893 LDEBUG << "FsaAccessBuilderRandom16::suppressEdge("
894 << from << ", " << to << ", " << currentChar << ","
895 << LimaString(*word_content) << ", " << wordOffset << ")";
896#else
897 LIMA_UNUSED(to)
898 LIMA_UNUSED(word_content)
899#endif
900 dicoGraph_traits16<graphType>::nconst_vtext_map_type vtext_map =
901 boost::get(vertex_text,m_graph);
902 dicoGraph_traits16<graphType>::nconst_vname_map_type vname_map =
903 boost::get(boost::vertex_name,m_graph);
904 dicoGraph_traits16<graphType>::nconst_vcount_map_type vcount_map =
905 boost::get(vertex_count,m_graph);
906
907 Lima::LimaString& text = get(vtext_map,from);
908 VERTEX_PROPERTY_16 vval = get(vname_map, from);
909 VERTEX_PROPERTY_16 qualif = vval & QUALITY_16;
910 VERTEX_PROPERTY_16 highCharTextPos = vval & TEXT_POS_16;
911
912 // tableau des coefficients
913 std::vector<int>& counts = get(vcount_map,from);
914 graphType::degree_size_type outd0 = boost::out_degree(from, m_graph);
915 Q_ASSERT( outd0 > 0 );
916 if( outd0 > 1 )
917 Q_ASSERT( (counts.size()+1) == outd0 );
918 else
919 Q_ASSERT( counts.size() == 0 );
920
921 int32_t textOffset0;
922 if( wordOffset == 1 ) {
923 if( highCharTextPos > 0 ) {
924 textOffset0 = findOffsetToInsertBefore( currentChar, text, 0, highCharTextPos, wordOffset );
925 }
926 else
927 textOffset0 = 0;
928
929 // Memorisation des transitions au dela de textOffset
930 std::list<dicoVertex> newOrderedTargetList;
931
932 // degree_size_type size = out_degree(from, m_graph);
933 // iterator to duplicate the list of out_edges
934 boost::graph_traits<graphType>::out_edge_iterator ei, edge_end;
935 boost::tie(ei,edge_end) = boost::out_edges(from,m_graph);
936 int32_t textOffset(0);
937 // fill the list up to the new transition to be created
938 std::vector<int>::iterator cIt = counts.begin();
939 for( ; ei != edge_end ; ei++, cIt++ ) {
940 if( textOffset == textOffset0 )
941 break;
942#ifdef DEBUG_CD
943// LDEBUG << "FsaAccessBuilderRandom16::suppressEdge: newOrderedTargetList.push_back("
944// << *ei << ") (1)";
945#endif
946 newOrderedTargetList.push_back(target(*ei,m_graph));
947 textOffset++;
948 }
949
950 // skip edge
951 if (outd0 > 1 )
952 counts.pop_back();
953 ei++;
954 // adjust highCharTextPos
955 highCharTextPos--;
956
957 // fill the end of the list
958 for( ; ei != edge_end ; ei++ ) {
959#ifdef DEBUG_CD
960// LDEBUG << "FsaAccessBuilderRandom16::suppressEdge: newOrderedTargetList.push_back("
961// << *ei << ") (2)";
962#endif
963 newOrderedTargetList.push_back(target(*ei,m_graph));
964 }
965 // remove all out_edges
966#ifdef DEBUG_CD
967 LDEBUG << "FsaAccessBuilderRandom16::suppressEdge: clear_edge("
968 << from << ")";
969#endif
970 clear_out_edges(from, m_graph);
971 Q_ASSERT(boost::out_degree(from, m_graph) == 0);
972 // add new list of out_edges
973 for( std::list<dicoVertex>::iterator vIt = newOrderedTargetList.begin() ;
974 vIt != newOrderedTargetList.end() ; vIt++ ) {
975#ifdef DEBUG_CD
976 LDEBUG << "FsaAccessBuilderRandom16::suppressEdge: add_edge("
977 << from << "," << *vIt << "";
978#endif
979 add_edge(from, *vIt, m_graph );
980 }
981 // from has been modified
982 // set vertex "from" as possibly no more "head of class"
983 qualif = qualif & (~HEAD_OF_CLASS_16);
984#ifdef DEBUG_CD
985 LDEBUG << "FsaAccessBuilderRandom16::suppressEdge: put(vname_map,"
986 << from << "," << qualif << " | " << highCharTextPos << "";
987#endif
988 put(vname_map, from, qualif | highCharTextPos);
989#ifdef DEBUG_CD
990 LDEBUG << "FsaAccessBuilderRandom16::suppressEdge: text("
991// << from << ")=" << get(vtext_map,from);
992 << from << ")=";
993 LDEBUG << "FsaAccessBuilderRandom16::suppressEdge: text="
994// << text;
995 ;
996// Lima::LimaString textpart = LimaString(word_content).left(wordOffset);
997 LDEBUG << "FsaAccessBuilderRandom16::suppressEdge: text.erase("
998// << textOffset0 << "," << textpart << ")";
999 << textOffset0 << "," << ")";
1000#endif
1001 text.remove(textOffset0, wordOffset);
1002#ifdef DEBUG_CD
1003 LDEBUG << "FsaAccessBuilderRandom16::suppressEdge: text("
1004// << from << ")=" << get(vtext_map,from);
1005 << from << ")=";
1006 LDEBUG << "FsaAccessBuilderRandom16::suppressEdge: text="
1007// << text;
1008 ;
1009#endif
1010 }
1011 else {
1012#ifdef DEBUG_CD
1013 LDEBUG << "FsaAccessBuilderRandom16::suppressEdge: findOffsetToInsertBefore("
1014// << currentChar << "," << text << ")";
1015 << currentChar << "," << ")";
1016#endif
1017 textOffset0 = findOffsetToInsertBefore( currentChar, text, highCharTextPos, text.length(), wordOffset );
1018 // TODO:
1019 Q_ASSERT(false);
1020 }
1021
1022 // check
1023 graphType::degree_size_type outd = boost::out_degree(from, m_graph);
1024 Q_ASSERT((outd+1) == outd0);
1025 Q_ASSERT( (get(vname_map, from)&TEXT_POS_16) == outd );
1026 if( outd > 0 )
1027 Q_ASSERT( (counts.size()+1) == outd );
1028 else
1029 Q_ASSERT( counts.size() == 0 );
1030 Lima::LimaString& textCheck = get(vtext_map,from);
1031 Q_ASSERT( static_cast<graphType::degree_size_type>(textCheck.size()) == outd );
1032}
1033
1034
1035void FsaAccessBuilderRandom16::replaceOrRegister( dicoVertex candidateState,
1036 PrefixIterator* prefixIt ){
1037// const LimaChar* word_content, int word_length, int32_t wordPos ) throw( AccessByStringNotInitialized ) {
1038#ifdef DEBUG_CD
1039 FSAALOGINIT;
1040 LDEBUG << "FsaAccessBuilderRandom16::replaceOrRegister: (" << candidateState << ")";
1041#endif
1042
1043 // check if leaf
1044 // degree_size_type nbChild = out_degree(dicoVertex, m_graph);
1045 // if( nbChild == 0)
1046 dico_degree_size nbChild = boost::out_degree(candidateState, m_graph);
1047 if( nbChild == 0 ) {
1048#ifdef DEBUG_CD
1049 LDEBUG << "FsaAccessBuilderRandom16::replaceOrRegister: out_degree = 0";
1050#endif
1051 return;
1052 }
1053
1054 // get first char (or last one if reverse) of word to search for in graph
1055 int32_t wordOffset;
1056 Q_ASSERT( prefixIt->hasNextLetter() );
1057 char32_t currentChar = prefixIt->getNextLetter(wordOffset);
1058
1059#ifdef DEBUG_CD
1060 LDEBUG << "FsaAccessBuilderRandom16::replaceOrRegister: currentChar="
1061 << currentChar << ")";
1062#endif
1063
1064 dicoGraph_traits16<graphType>::nconst_vtext_map_type vtext_map =
1065 boost::get(vertex_text,m_graph);
1066 dicoGraph_traits16<graphType>::nconst_vname_map_type vname_map =
1067 boost::get(boost::vertex_name,m_graph);
1068 // find the path in the atomaton defined by the prefix
1069 int32_t edgeOffset = 0;
1070 int32_t textOffset = 0;
1071 Lima::LimaString& text = get(vtext_map,candidateState);
1072#ifdef DEBUG_CD
1073 std::string text8 = LimaString(text.data()).toStdString();
1074 LDEBUG << "FsaAccessBuilderRandom16::replaceOrRegister: text = " << text8.c_str();
1075#endif
1076 int32_t highCharTextPos = get(vname_map,candidateState)&TEXT_POS_16;
1077 if( wordOffset == 1 ) {
1078 textOffset = findEdge( currentChar, text, 0, highCharTextPos, wordOffset );
1079 edgeOffset = textOffset;
1080 }
1081 else {
1082 textOffset = findEdge( currentChar, text, highCharTextPos, text.length(), wordOffset );
1083 edgeOffset = highCharTextPos + (textOffset - highCharTextPos)/2;
1084 }
1085
1086 if( edgeOffset >= 0 ) {
1087 prefixIt->next(wordOffset);
1088 boost::graph_traits<graphType>::out_edge_iterator ei, edge_end;
1089 boost::tie(ei,edge_end) = boost::out_edges(candidateState,m_graph);
1090 dicoEdgeType edge = *(ei+edgeOffset);
1091 boost::graph_traits<graphType>::vertex_descriptor lastChild = target(edge, m_graph);
1092
1093// replaceOrRegister( lastChild, word_content, word_length, wordPos );
1094 replaceOrRegister( lastChild, prefixIt );
1095
1096 std::pair<const dicoVertex,bool> equivalent = findEquivalentInRegister( lastChild );
1097 if( equivalent.second ) {
1098 ForwardPrefixIterator textIt( text, textOffset );
1099 merge( equivalent.first, lastChild, candidateState, textIt );
1100 }
1101 else {
1102#ifdef DEBUG_CD
1103 LDEBUG << "FsaAccessBuilderRandom16::replaceOrRegister: m_register.push_back("
1104 << lastChild << ")";
1105#endif
1106 dicoGraph_traits16<graphType>::nconst_vname_map_type vname_map =
1107 boost::get(boost::vertex_name,m_graph);
1108 put(vname_map,lastChild, get(vname_map,lastChild)|HEAD_OF_CLASS_16);
1109 }
1110 }
1111 else {
1112 std::string mess("FsaAccessBuilderRandom16::replaceOrRegister: no path to reach 0degreeVertex!!");
1113#ifdef DEBUG_CD
1114 LERROR << mess.c_str() ;
1115#endif
1116 throw( AccessByStringNotInitialized( mess ) );
1117 }
1118
1119}
1120
1121void FsaAccessBuilderRandom16::merge( dicoVertex inRegister,
1122 dicoVertex tempState, dicoVertex parentState,
1123 const ForwardPrefixIterator& textIt) {
1124#ifdef DEBUG_CD
1125 FSAALOGINIT;
1126 LDEBUG << "FsaAccessBuilderRandom16::merge( " << inRegister << ", "
1127 << tempState << ", "
1128 << parentState << ")";
1129#endif
1130 // find in transition parentState -> tempstate
1131 std::pair<dicoEdgeType, bool> trans = edge(parentState, tempState, m_graph);
1132 Q_ASSERT( trans.second );
1133 // forward this transition to inRegister
1134 if( trans.second ) {
1135#ifdef DEBUG_CD
1136 LDEBUG << "FsaAccessBuilderRandom16::merge: replaceEdge(" << parentState << ", "
1137 << inRegister << ", "
1138 << ")";
1139#endif
1140
1141 int32_t wordOffset;
1142 char32_t currentChar = textIt.getNextLetter(wordOffset);
1143 replaceEdge( parentState, inRegister, currentChar, wordOffset );
1144
1145// std::pair<dicoEdgeType, bool> res = add_edge(parentState, inRegister, m_graph);
1146// Q_ASSERT( res.second );
1147 }
1148
1149 // delete tempstate
1150 clear_vertex(tempState, m_graph);
1151 remove_vertex(tempState, m_graph);
1152}
1153
1154
1155// mise �jour des coefficients
1156int FsaAccessBuilderRandom16::updateHash( dicoVertex from,
1157 PrefixIterator* prefixIt ) {
1158// const LimaChar* word_content, int word_length, int32_t wordPos ) throw( AccessByStringNotInitialized ) {
1159#ifdef DEBUG_CD
1160 FSAALOGINIT;
1161 std::ostringstream stro1(std::ios::in | std::ios::out);
1162 stro1 << from << "(nbChild=" << boost::out_degree(from, m_graph) << "), " << *prefixIt;
1163 LDEBUG << "FsaAccessBuilderRandom16::updateHash("
1164 << stro1.str().c_str() << ")";
1165#endif
1166
1167 dicoGraph_traits16<graphType>::nconst_vname_map_type vname_map =
1168 boost::get(boost::vertex_name,m_graph);
1169 dicoGraph_traits16<graphType>::nconst_vcount_map_type vcount_map =
1170 boost::get(vertex_count,m_graph);
1171 dicoGraph_traits16<graphType>::nconst_vtext_map_type vtext_map =
1172 boost::get(vertex_text,m_graph);
1173
1174 // vocabulaire du sous_graphe
1175 int total(0);
1176 // tableau des coefficients
1177 std::vector<int>& counts = get(vcount_map,from);
1178 VERTEX_PROPERTY_16 val = get(vname_map, from);
1179
1180 // check if leaf
1181 // degree_size_type nbChild = out_degree(dicoVertex, m_graph);
1182 // if( nbChild == 0)
1183 dico_degree_size nbChild = boost::out_degree(from, m_graph);
1184 if( nbChild == 0 ) {
1185#ifdef DEBUG_CD
1186 LDEBUG << "FsaAccessBuilderRandom16::updateHash: out_degree = 0";
1187#endif
1188 // On ajoute le noeud courant s'il est final
1189 if( (val & FINAL_16) == FINAL_16 ) {
1190#ifdef DEBUG_CD
1191 LDEBUG << "FsaAccessBuilderRandom16::updateHash: FINAL node, increment " << total ;
1192#endif
1193 total++;
1194 }
1195 return total;
1196 }
1197#ifdef DEBUG_CD
1198 if( nbChild > 1 )
1199 Q_ASSERT(nbChild == (counts.size()+1) );
1200 else
1201 Q_ASSERT( counts.size() == 0 );
1202#endif
1203
1204 // get first char (or last one if reverse) of word to search for in graph
1205 int32_t wordOffset;
1206 // find the path in the atomaton defined by the prefix
1207 int32_t edgeOffset = 0;
1208 int32_t textOffset = 0;
1209 if( prefixIt->hasNextLetter() ) {
1210 char32_t currentChar = prefixIt->getNextLetter((int32_t&)wordOffset);
1211#ifdef DEBUG_CD
1212 LDEBUG << "FsaAccessBuilderRandom16::updateHash: currentChar="
1213 << currentChar << ")";
1214#endif
1215
1216 Lima::LimaString& text = get(vtext_map,from);
1217#ifdef DEBUG_CD
1218 std::string text8 = Lima::Common::Misc::limastring2utf8stdstring(LimaString(text.data()));
1219 LDEBUG << "FsaAccessBuilderRandom16::updateHash: text = " << text8.c_str();
1220#endif
1221 int32_t highCharTextPos = val&TEXT_POS_16;
1222 if( wordOffset == 1 ) {
1223 textOffset = findEdge( currentChar, text, 0, highCharTextPos, wordOffset );
1224 edgeOffset = textOffset;
1225 }
1226 else {
1227 textOffset = findEdge( currentChar, text, highCharTextPos, text.length(), wordOffset );
1228 edgeOffset = highCharTextPos + (textOffset - highCharTextPos)/2;
1229 }
1230 prefixIt->next(wordOffset);
1231 }
1232 else {
1233 edgeOffset = 0;
1234 textOffset = 0;
1235 }
1236
1237 if( edgeOffset >= 0 ) {
1238 boost::graph_traits<graphType>::out_edge_iterator ei, edge_end;
1239 boost::tie(ei,edge_end) = boost::out_edges(from,m_graph);
1240 dicoEdgeType edge = *(ei+edgeOffset);
1241 boost::graph_traits<graphType>::vertex_descriptor lastChild = target(edge, m_graph);
1242 // On met �jour les coefficients sur le sous arbre modifi�// int subtotal = updateHash( lastChild, word_content, word_length, wordPos );
1243 int subtotal = updateHash( lastChild, prefixIt );
1244
1245 // nombre de sous automates
1246 graphType::degree_size_type outd = boost::out_degree(from, m_graph);
1247 // On saute les sous-arbres jusqu'au sous arbre modifié
1248 std::vector<int>::iterator cIt = counts.begin();
1249#ifdef DEBUG_CD
1250 LDEBUG << "FsaAccessBuilderRandom16::updateHash: counts.size()="
1251 << counts.size();
1252#endif
1253 int32_t i = 0;
1254 for( ; (i+1 < static_cast<int32_t>(outd)) && (i<edgeOffset) ; ei++ , i++, cIt++ ) {
1255 Q_ASSERT(ei != edge_end);
1256 total = total + *cIt;
1257 }
1258 // On calcul la mise a jour a faire sur le tableau de coefficients
1259 int delta = 0;
1260 if( i+1 < static_cast<int32_t>(outd) ){
1261#ifdef DEBUG_CD
1262 LDEBUG << "FsaAccessBuilderRandom16::updateHash: i="
1263 << i << ",total=" << total << ", subtotal=" << subtotal;
1264#endif
1265 delta = (total + subtotal) - *cIt;
1266 *cIt = total + subtotal;
1267 ei++;
1268 i++;
1269 cIt++;
1270 }
1271 // On modifie les coefficients sur la suite du tableau
1272 for( ; i+1 < static_cast<int32_t>(outd) ; ei++ , i++, cIt++ ) {
1273#ifdef DEBUG_CD
1274 LDEBUG << "FsaAccessBuilderRandom16::updateHash: i="
1275 << i << ",*cIt=" << *cIt << ", delta=" << delta;
1276#endif
1277 Q_ASSERT(ei != edge_end);
1278 total = *cIt + delta;
1279 *cIt = total;
1280 }
1281
1282 // On calcul le dernier puisqu'il n'a pas memorise
1283 if( ei != edge_end ) {
1284#ifdef DEBUG_CD
1285// LDEBUG << "FsaAccessBuilderRandom16::updateHash: call computeHash("
1286// << target(*ei,m_graph) << ")";
1287#endif
1288 int subtotal = computeHash( target(*ei,m_graph) );
1289 total = total + subtotal;
1290 }
1291 put(vname_map, from, get(vname_map, from) | SET_16);
1292 // On ajoute le noeud courant s'il est final
1293 if( (val & FINAL_16) == FINAL_16 ) {
1294#ifdef DEBUG_CD
1295 LDEBUG << "FsaAccessBuilderRandom16::updateHash: FINAL node, increment " << total ;
1296#endif
1297 total++;
1298 }
1299#ifdef DEBUG_CD
1300 LDEBUG << "FsaAccessBuilderRandom16::updateHash: return " << total ;
1301#endif
1302 return total;
1303 }
1304 else {
1305 std::string mess("FsaAccessBuilderRandom16::updateHash: no path to reach 0degreeVertex!!");
1306#ifdef DEBUG_CD
1307 LERROR << mess.c_str() ;
1308#endif
1309 throw( AccessByStringNotInitialized( mess ) );
1310 }
1311}
1312
1313void FsaAccessBuilderRandom16::addSuffix( dicoVertex from, PrefixIterator* prefixIt ) {
1314#ifdef DEBUG_CD
1315 FSAALOGINIT;
1316 Lima::LimaString s = prefixIt->getCurrentPrefix();
1317 LDEBUG << "FsaAccessBuilderRandom16::addSuffix: (" << from
1318 << ", " << s << ")";
1319#endif
1320
1321 dicoGraph_traits16<graphType>::nconst_vname_map_type vname_map =
1322 boost::get(boost::vertex_name,m_graph);
1323
1324 int32_t prefixOffset;
1325 dicoVertex to = from;
1326 for( ; prefixIt->hasNextLetter() ; prefixIt->next(prefixOffset) ) {
1327
1328 to = add_vertex(m_graph);
1329 put(vname_map, to, 0);
1330
1331 char32_t letter = prefixIt->getNextLetter(prefixOffset);
1332#ifdef DEBUG_CD
1333 char buff[256];
1334 sprintf(buff, "letter = %04x, suffixPos=%d\n", letter, prefixIt->getExternalWordPos() );
1335 LDEBUG << buff;
1336#endif
1337
1338#ifdef DEBUG_CD
1339 LDEBUG << "FsaAccessBuilderRandom16::addSuffix: add_edge(" << from
1340 << ", " << to << ")";
1341#endif
1342
1343 addEdge( from, to, letter, prefixIt->getCurrentContent(), prefixOffset );
1344 from = to;
1345 }
1346#ifdef DEBUG_CD
1347 LDEBUG << "FsaAccessBuilderRandom16::addSuffix: put(vname_map, to="
1348 << to << ", " << FINAL_16 << ")";
1349#endif
1350 put(vname_map, to, FINAL_16);
1351}
1352
1353
1354
1355} // namespace FsaAccess
1356} // namespace Commmon
1357} // namespace Lima
vertex_text
@ vertex_text
Definition FsaAccess16.h:72
vertex_count
@ vertex_count
Definition FsaAccess16.h:74
VERTEX_PROPERTY_16
#define VERTEX_PROPERTY_16
Definition FsaAccessHeader.h:45
LWARN
#define LWARN
Definition LimaCommon.h:160
LIMA_UNUSED
#define LIMA_UNUSED(x)
Definition LimaCommon.h:224
LDEBUG
#define LDEBUG
Definition LimaCommon.h:157
LERROR
#define LERROR
Definition LimaCommon.h:161
FSAALOGINIT
#define FSAALOGINIT
Definition LimaCommon.h:206
FSAAIOLOGINIT
#define FSAAIOLOGINIT
Definition LimaCommon.h:205
Lima::AccessByStringNotInitialized
Use this exception to signal the used of a wrongly initialized LIMA dictionary.
Definition LimaCommon.h:428
Lima::Common::FsaAccess::FsaAccess16::getPrefix
void getPrefix(dicoVertexType &from, PrefixIterator *prefixIt) const
Recursively goes through the graph from from, following edges labelled by the prefix iterator chars.
Lima::Common::FsaAccess::FsaAccess16::findEdge
int32_t findEdge(const char32_t searchChar, const LimaString &textString, int32_t min, int range, int nb_unit_for_char) const
find the right offset in the vector of out_edge: search for the character currentChar in the string t...
Lima::Common::FsaAccess::FsaAccess16::equivalent
bool equivalent(dicoVertexType referenceState, dicoVertexType candidateState) const
are both state equivalent? We assume that edges are ordered
Lima::Common::FsaAccess::FsaAccess16::writeBody
void writeBody(AbstractFsaAccessOStreamWrapper &ow)
Lima::Common::FsaAccess::FsaAccess16::findEquivalentInRegister
std::pair< const dicoVertexType, bool > findEquivalentInRegister(dicoVertexType tempState)
Search for equivalent state in register.
Lima::Common::FsaAccess::FsaAccess16::getPrefixIterator
PrefixIterator * getPrefixIterator(const LimaString &word, const uint64_t offset=0) const
For all navigation Factory of prefixIterator (prefixIt depends on direction: forward/reverse)
Lima::Common::FsaAccess::FsaAccess16::dicoEdgeType
boost::graph_traits< graphType >::edge_descriptor dicoEdgeType
type of vertex descriptor type of edge descriptor
Definition FsaAccess16.h:186
Lima::Common::FsaAccess::FsaAccess16::findOffsetToInsertBefore
int32_t findOffsetToInsertBefore(const char32_t searchChar, const LimaString &textString, int32_t min, int range, int nb_unit_per_char) const
find where to insert currentChar in the string text using dichotomy search (assume characters are ord...
Lima::Common::FsaAccess::FsaAccessBuilderRandom16::getFsaAccessIOHandler
FsaAccessIOHandler< graphType > * getFsaAccessIOHandler() const override
For IO Factory of IO Handler: Handler depends on graphType: with mapping or not.
Definition FsaAccessBuilderRandom16.cpp:41
Lima::Common::FsaAccess::FsaAccessBuilderRandom16::addRandomWord
void addRandomWord(const Lima::LimaString &newWord) override
gives the number of entries
Definition FsaAccessBuilderRandom16.cpp:111
Lima::Common::FsaAccess::FsaAccessHeader::write
void write(AbstractFsaAccessOStreamWrapper &ow)
Definition FsaAccessHeader.cpp:240
Lima::Common::FsaAccess::FsaAccessHeader::setPackingStatus
void setPackingStatus(uint8_t packingStatus)
Definition FsaAccessHeader.cpp:111
Lima::Common::FsaAccess::FsaAccessReader16< selected_graph_types16::builderGraphType >::getSuperWords
virtual std::pair< AccessSuperWordIterator, AccessSuperWordIterator > getSuperWords(const LimaString &word) const override
Lima::Common::FsaAccess::FsaAccessReader16< selected_graph_types16::builderGraphType >::computeHash
int computeHash(typename boost::graph_traits< selected_graph_types16::builderGraphType >::vertex_descriptor from)
Lima::Common::FsaAccess::PrefixIterator::next
virtual void next(const int32_t wordOffset)=0
Lima::Common::FsaAccess::PrefixIterator::getCurrentContent
virtual const Lima::LimaChar * getCurrentContent() const =0
Lima::Common::FsaAccess::PrefixIterator::hasNextLetter
virtual bool hasNextLetter() const =0
Lima::Common::FsaAccess::PrefixIterator::getNextLetter
virtual char32_t getNextLetter(int32_t &wordOffset) const =0
Lima::Common::FsaAccess::PrefixIterator::getPastPrefix
virtual const LimaString getPastPrefix() const =0
Lima::Common::FsaAccess::PrefixIterator::getCurrentPrefix
virtual const LimaString getCurrentPrefix() const =0
Lima::Common::Misc::limastring2utf8stdstring
std::string limastring2utf8stdstring(const Lima::LimaString &phrase, uint32_t size0)
Convert a wide string to a string , in dest up to size bytes.
Definition strwstrtools.cpp:221
Lima
NAUTITIA.
Definition AmosePluginsManager.h:15
Lima::LimaChar
QChar LimaChar
Definition LimaString.h:30
Lima::LimaString
QString LimaString
Definition LimaString.h:33
Lima::Common::FsaAccess::dicoGraph_traits16::nconst_vcount_map_type
boost::property_map< graphType, vertex_count_t >::type nconst_vcount_map_type
Definition FsaAccess16.h:115
Lima::Common::FsaAccess::dicoGraph_traits16::nconst_vtext_map_type
boost::property_map< graphType, vertex_text_t >::type nconst_vtext_map_type
Definition FsaAccess16.h:108
Lima::Common::FsaAccess::dicoGraph_traits16::nconst_vname_map_type
boost::property_map< graphType, boost::vertex_name_t >::type nconst_vname_map_type
Definition FsaAccess16.h:101
Lima::Common::FsaAccess::selected_graph_types16
Definition FsaAccess16.h:119