1 // Copyright 2010-2018, Google Inc. 2 // All rights reserved. 3 // 4 // Redistribution and use in source and binary forms, with or without 5 // modification, are permitted provided that the following conditions are 6 // met: 7 // 8 // * Redistributions of source code must retain the above copyright 9 // notice, this list of conditions and the following disclaimer. 10 // * Redistributions in binary form must reproduce the above 11 // copyright notice, this list of conditions and the following disclaimer 12 // in the documentation and/or other materials provided with the 13 // distribution. 14 // * Neither the name of Google Inc. nor the names of its 15 // contributors may be used to endorse or promote products derived from 16 // this software without specific prior written permission. 17 // 18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 30 #ifndef MOZC_CONVERTER_NBEST_GENERATOR_H_ 31 #define MOZC_CONVERTER_NBEST_GENERATOR_H_ 32 33 #include <memory> 34 #include <string> 35 #include <vector> 36 37 #include "base/freelist.h" 38 #include "base/port.h" 39 #include "converter/candidate_filter.h" 40 #include "converter/segments.h" 41 #include "dictionary/suppression_dictionary.h" 42 #include "dictionary/pos_matcher.h" 43 44 namespace mozc { 45 46 class Connector; 47 class Lattice; 48 class Segmenter; 49 class SuggestionFilter; 50 struct Node; 51 52 class NBestGenerator { 53 public: 54 enum BoundaryCheckMode { 55 // Boundary check mode. 56 // For the case like; 57 // Candidate edge: | candidate | 58 // Nodes: |Node A|Node B|Node C|Node D| 59 60 // For normal converison. 61 // Candidate boundary is strictly same as inner boundary. 62 // A-B: Should be the boundary 63 // B-C: Should not be the boundary 64 // C-D: Should be the boundary 65 STRICT = 0, 66 67 // For resegmented segment. 68 // Check mid point only. 69 // A-B: Don't care 70 // B-C: Should not be the boundary 71 // C-D: Don't care 72 ONLY_MID, 73 74 // For Realtime conversion ("私の名前は中野です"). 75 // Check only for candidate edge. 76 // A-B: Should be the boundary 77 // B-C: Don't care 78 // C-D: Should be the boundary 79 ONLY_EDGE, 80 }; 81 82 // Try to enumurate N-best results between begin_node and end_node. 83 NBestGenerator( 84 const dictionary::SuppressionDictionary *suppression_dictionary, 85 const Segmenter *segmenter, 86 const Connector *connector, 87 const dictionary::POSMatcher *pos_matcher, 88 const Lattice *lattice, 89 const SuggestionFilter *suggestion_filter, 90 bool apply_suggestion_filter_for_exact_match); 91 ~NBestGenerator(); 92 93 // Reset the iterator status. 94 void Reset(const Node *begin_node, const Node *end_node, 95 const BoundaryCheckMode mode); 96 97 // Iterator: 98 // Can obtain N-best results by calling Next() in sequence. 99 bool Next(const string &original_key, 100 Segment::Candidate *candidate, 101 Segments::RequestType request_type); 102 103 private: 104 enum BoundaryCheckResult { 105 VALID = 0, 106 VALID_WEAK_CONNECTED, // Valid but should get penalty. 107 INVALID, 108 }; 109 110 typedef BoundaryCheckResult (NBestGenerator::*BoundaryChecker)( 111 const Node *, const Node *, bool) const; 112 113 struct QueueElement; 114 struct QueueElementComparator; 115 116 // This is just a priority_queue of const QueueElement*, but supports 117 // more operations in addition to std::priority_queue. 118 class Agenda { 119 public: Agenda()120 Agenda() { 121 } ~Agenda()122 ~Agenda() { 123 } 124 Top()125 const QueueElement *Top() const { 126 return priority_queue_.front(); 127 } IsEmpty()128 bool IsEmpty() const { 129 return priority_queue_.empty(); 130 } Clear()131 void Clear() { 132 priority_queue_.clear(); 133 } Reserve(int size)134 void Reserve(int size) { 135 priority_queue_.reserve(size); 136 } 137 138 void Push(const QueueElement *element); 139 void Pop(); 140 141 private: 142 std::vector<const QueueElement*> priority_queue_; 143 144 DISALLOW_COPY_AND_ASSIGN(Agenda); 145 }; 146 147 int InsertTopResult(const string &original_key, 148 Segment::Candidate *candidate, 149 Segments::RequestType request_type); 150 151 void MakeCandidate(Segment::Candidate *candidate, 152 int32 cost, int32 structure_cost, int32 wcost, 153 const std::vector<const Node *> &nodes) const; 154 155 // Helper functions for Next(). Checks node boundary conditions. 156 BoundaryCheckResult CheckStrict( 157 const Node *lnode, const Node *rnode, bool is_edge) const; 158 BoundaryCheckResult CheckOnlyMid( 159 const Node *lnode, const Node *rnode, bool is_edge) const; 160 BoundaryCheckResult CheckOnlyEdge( 161 const Node *lnode, const Node *rnode, bool is_edge) const; 162 163 int GetTransitionCost(const Node *lnode, const Node *rnode) const; 164 165 // Create queue element from freelist 166 const QueueElement *CreateNewElement(const Node *node, 167 const QueueElement *next, 168 int32 fx, 169 int32 gx, 170 int32 structure_gx, 171 int32 w_gx); 172 173 // References to relevant modules. 174 const dictionary::SuppressionDictionary *suppression_dictionary_; 175 const Segmenter *segmenter_; 176 const Connector *connector_; 177 const dictionary::POSMatcher *pos_matcher_; 178 const Lattice *lattice_; 179 180 const Node *begin_node_; 181 const Node *end_node_; 182 183 Agenda agenda_; 184 FreeList<QueueElement> freelist_; 185 std::vector<const Node *> nodes_; 186 std::unique_ptr<converter::CandidateFilter> filter_; 187 bool viterbi_result_checked_; 188 BoundaryCheckMode check_mode_; 189 190 BoundaryChecker boundary_checker_; 191 192 DISALLOW_COPY_AND_ASSIGN(NBestGenerator); 193 }; 194 195 } // namespace mozc 196 197 #endif // MOZC_CONVERTER_NBEST_GENERATOR_H_ 198