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