diff options
author | Chris Dyer <redpony@gmail.com> | 2014-12-18 12:52:00 -0500 |
---|---|---|
committer | Chris Dyer <redpony@gmail.com> | 2014-12-18 12:52:00 -0500 |
commit | 59befb84d2879bb9b50eaa974471155caefbc55f (patch) | |
tree | 8ceea539890f3faaa5a35303bf6293536e6e63fb | |
parent | 3b3d7fe1f65c811d2c158f0c79a007817023a5c5 (diff) | |
parent | d426bbfed039f1b8ab0ebbea9745f6e827a40af1 (diff) |
Merge pull request #64 from kho/softsyn_2
Proper implementation of soft syntactic constraint features
-rw-r--r-- | decoder/Makefile.am | 2 | ||||
-rw-r--r-- | decoder/cdec_ff.cc | 2 | ||||
-rw-r--r-- | decoder/ff_soft_syn.cc | 265 | ||||
-rw-r--r-- | decoder/ff_soft_syn.h | 38 |
4 files changed, 307 insertions, 0 deletions
diff --git a/decoder/Makefile.am b/decoder/Makefile.am index f9f90cfb..dbec532e 100644 --- a/decoder/Makefile.am +++ b/decoder/Makefile.am @@ -61,6 +61,7 @@ libcdec_a_SOURCES = \ ff_rules.h \ ff_ruleshape.h \ ff_sample_fsa.h \ + ff_soft_syn.h \ ff_soft_syntax.h \ ff_soft_syntax_mindist.h \ ff_source_path.h \ @@ -125,6 +126,7 @@ libcdec_a_SOURCES = \ ff_parse_match.cc \ ff_rules.cc \ ff_ruleshape.cc \ + ff_soft_syn.cc \ ff_soft_syntax.cc \ ff_soft_syntax_mindist.cc \ ff_source_path.cc \ diff --git a/decoder/cdec_ff.cc b/decoder/cdec_ff.cc index 6f7227aa..973a643a 100644 --- a/decoder/cdec_ff.cc +++ b/decoder/cdec_ff.cc @@ -15,6 +15,7 @@ #include "ff_rules.h" #include "ff_ruleshape.h" #include "ff_bleu.h" +#include "ff_soft_syn.h" #include "ff_soft_syntax.h" #include "ff_soft_syntax_mindist.h" #include "ff_source_path.h" @@ -80,4 +81,5 @@ void register_feature_functions() { ff_registry.Register("WordSet", new FFFactory<WordSet>); ff_registry.Register("ConstReorderFeature", new FFFactory<ConstReorderFeature>); ff_registry.Register("External", new FFFactory<ExternalFeature>); + ff_registry.Register("SoftSynFeature", new SoftSynFeatureFactory()); } diff --git a/decoder/ff_soft_syn.cc b/decoder/ff_soft_syn.cc new file mode 100644 index 00000000..2d4369d1 --- /dev/null +++ b/decoder/ff_soft_syn.cc @@ -0,0 +1,265 @@ +/* + * ff_soft_syn.cc + * + */ +#include "ff_soft_syn.h" + +#include "filelib.h" +#include "stringlib.h" +#include "hg.h" +#include "sentence_metadata.h" +#include "ff_const_reorder_common.h" + +#include <string> +#include <vector> +#include <stdio.h> + +using namespace std; +using namespace const_reorder; + +typedef HASH_MAP<std::string, vector<string> > MapFeatures; + +struct SoftSynFeatureImpl { + SoftSynFeatureImpl(const string& /*params*/) { + parsed_tree_ = NULL; + map_features_ = NULL; + } + + ~SoftSynFeatureImpl() { FreeSentenceVariables(); } + + void InitializeInputSentence(const std::string& parse_file) { + FreeSentenceVariables(); + parsed_tree_ = ReadParseTree(parse_file); + + // we can do the features "off-line" + map_features_ = new MapFeatures(); + InitializeFeatures(map_features_); + } + + /* + * ff_const_reorder.cc::ConstReorderFeatureImpl also defines this function + */ + void FindConsts(const SParsedTree* tree, int begin, int end, + vector<STreeItem*>& consts) { + STreeItem* item; + item = tree->m_vecTerminals[begin]->m_ptParent; + while (true) { + while (item->m_ptParent != NULL && + item->m_ptParent->m_iBegin == item->m_iBegin && + item->m_ptParent->m_iEnd <= end) + item = item->m_ptParent; + + if (item->m_ptParent == NULL && item->m_vecChildren.size() == 1 && + strcmp(item->m_pszTerm, "ROOT") == 0) + item = item->m_vecChildren[0]; // we automatically add a "ROOT" node at + // the top, skip it if necessary. + + consts.push_back(item); + if (item->m_iEnd < end) + item = tree->m_vecTerminals[item->m_iEnd + 1]->m_ptParent; + else + break; + } + } + + /* + * according to Marton & Resnik (2008) + * a span cann't have both X+ style and X= style features + * a constituent XP is crossed only if the span not only covers parts of XP's + *content, but also covers one or more words outside XP + * a span may have X+, Y+ + * + * (note, we refer X* features to X= features in Marton & Resnik (2008)) + */ + void GenerateSoftFeature(int begin, int end, const SParsedTree* tree, + vector<string>& vecFeature) { + vector<STreeItem*> vecNode; + FindConsts(tree, begin, end, vecNode); + + if (vecNode.size() == 1) { + // match to one constituent + string feature_name = string(vecNode[0]->m_pszTerm) + string("*"); + vecFeature.push_back(feature_name); + } else { + // match to multiple constituents, find the lowest common parent (lcp) + STreeItem* lcp = vecNode[0]; + while (lcp->m_iEnd < end) lcp = lcp->m_ptParent; + + for (size_t i = 0; i < vecNode.size(); i++) { + STreeItem* item = vecNode[i]; + + while (item != lcp) { + if (item->m_iBegin < begin || item->m_iEnd > end) { + // item is crossed + string feature_name = string(item->m_pszTerm) + string("+"); + vecFeature.push_back(feature_name); + } + if (item->m_iBrotherIndex > 0 && + item->m_ptParent->m_vecChildren[item->m_iBrotherIndex - 1] + ->m_iBegin >= begin && + item->m_ptParent->m_vecChildren[item->m_iBrotherIndex - 1] + ->m_iEnd <= end) + break; // we don't want to collect crossed constituents twice + item = item->m_ptParent; + } + } + } + } + + void GenerateSoftFeatureFromFlattenedTree(int begin, int end, + const SParsedTree* tree, + vector<string>& vecFeature) { + vector<STreeItem*> vecNode; + FindConsts(tree, begin, end, vecNode); + + if (vecNode.size() == 1) { + // match to one constituent + string feature_name = string(vecNode[0]->m_pszTerm) + string("*"); + vecFeature.push_back(feature_name); + } else { + // match to multiple constituents, see if they have a common parent + size_t i = 0; + for (i = 1; i < vecNode.size(); i++) { + if (vecNode[i]->m_ptParent != vecNode[0]->m_ptParent) break; + } + if (i == vecNode.size()) { + // they share a common parent + string feature_name = + string(vecNode[0]->m_ptParent->m_pszTerm) + string("&"); + vecFeature.push_back(feature_name); + } else { + // they don't share a common parent, find the lowest common parent (lcp) + STreeItem* lcp = vecNode[0]; + while (lcp->m_iEnd < end) lcp = lcp->m_ptParent; + + for (size_t i = 0; i < vecNode.size(); i++) { + STreeItem* item = vecNode[i]; + + while (item != lcp) { + if (item->m_iBegin < begin || item->m_iEnd > end) { + // item is crossed + string feature_name = string(item->m_pszTerm) + string("+"); + vecFeature.push_back(feature_name); + } + if (item->m_iBrotherIndex > 0 && + item->m_ptParent->m_vecChildren[item->m_iBrotherIndex - 1] + ->m_iBegin >= begin && + item->m_ptParent->m_vecChildren[item->m_iBrotherIndex - 1] + ->m_iEnd <= end) + break; // we don't want to collect crossed constituents twice + item = item->m_ptParent; + } + } + } + } + } + + void SetSoftSynFeature(const Hypergraph::Edge& edge, + SparseVector<double>* features) { + if (parsed_tree_ == NULL) return; + + // soft feature for the whole span + const vector<string> vecFeature = + GenerateSoftFeature(edge.i_, edge.j_ - 1, map_features_); + for (size_t i = 0; i < vecFeature.size(); i++) { + int f_id = FD::Convert(vecFeature[i]); + if (f_id) features->set_value(f_id, 1); + } + } + + private: + const vector<string>& GenerateSoftFeature(int begin, int end, + MapFeatures* map_features) { + string key; + GenerateKey(begin, end, key); + MapFeatures::const_iterator iter = (*map_features).find(key); + assert(iter != map_features->end()); + return iter->second; + } + + void Byte_to_Char(unsigned char* str, int n) { + str[0] = (n & 255); + str[1] = n / 256; + } + + void GenerateKey(int begin, int end, string& key) { + unsigned char szTerm[1001]; + Byte_to_Char(szTerm, begin); + Byte_to_Char(szTerm + 2, end); + szTerm[4] = '\0'; + key = string(szTerm, szTerm + 4); + } + + void InitializeFeatures(MapFeatures* map_features) { + if (parsed_tree_ == NULL) return; + + for (size_t i = 0; i < parsed_tree_->m_vecTerminals.size(); i++) + for (size_t j = i; j < parsed_tree_->m_vecTerminals.size(); j++) { + vector<string> vecFeature; + GenerateSoftFeature(i, j, parsed_tree_, vecFeature); + string key; + GenerateKey(i, j, key); + (*map_features)[key] = vecFeature; + } + } + + void FreeSentenceVariables() { + if (parsed_tree_ != NULL) delete parsed_tree_; + if (map_features_ != NULL) delete map_features_; + } + + SParsedTree* ReadParseTree(const std::string& parse_file) { + SParseReader* reader = new SParseReader(parse_file.c_str(), false); + SParsedTree* tree = reader->fnReadNextParseTree(); + // assert(tree != NULL); + delete reader; + return tree; + } + + private: + SParsedTree* parsed_tree_; + + MapFeatures* map_features_; +}; + +SoftSynFeature::SoftSynFeature(std::string param) { + pimpl_ = new SoftSynFeatureImpl(param); + name_ = "SoftSynFeature"; +} + +SoftSynFeature::~SoftSynFeature() { delete pimpl_; } + +void SoftSynFeature::PrepareForInput(const SentenceMetadata& smeta) { + string parse_file = smeta.GetSGMLValue("parse"); + if (parse_file.empty()) { + parse_file = smeta.GetSGMLValue("src_tree"); + } + assert(parse_file.size()); + pimpl_->InitializeInputSentence(parse_file); +} + +void SoftSynFeature::TraversalFeaturesImpl( + const SentenceMetadata& /*smeta*/, const Hypergraph::Edge& edge, + const vector<const void*>& /*ant_states*/, SparseVector<double>* features, + SparseVector<double>* /*estimated_features*/, void* /*state*/) const { + pimpl_->SetSoftSynFeature(edge, features); +} + +string SoftSynFeature::usage(bool /*param*/, bool /*verbose*/) { + return "SoftSynFeature"; +} + +boost::shared_ptr<FeatureFunction> CreateSoftSynFeatureModel( + std::string param) { + SoftSynFeature* ret = new SoftSynFeature(param); + return boost::shared_ptr<FeatureFunction>(ret); +} + +boost::shared_ptr<FeatureFunction> SoftSynFeatureFactory::Create( + std::string param) const { + return CreateSoftSynFeatureModel(param); +} + +std::string SoftSynFeatureFactory::usage(bool params, bool verbose) const { + return SoftSynFeature::usage(params, verbose); +} diff --git a/decoder/ff_soft_syn.h b/decoder/ff_soft_syn.h new file mode 100644 index 00000000..df9a6cc8 --- /dev/null +++ b/decoder/ff_soft_syn.h @@ -0,0 +1,38 @@ +/* + * ff_soft_syn.h + * + */ + +#ifndef FF_SOFT_SYN_H_ +#define FF_SOFT_SYN_H_ + +#include "ff_factory.h" +#include "ff.h" + +struct SoftSynFeatureImpl; + +class SoftSynFeature : public FeatureFunction { + public: + SoftSynFeature(std::string param); + ~SoftSynFeature(); + static std::string usage(bool param, bool verbose); + + protected: + virtual void PrepareForInput(const SentenceMetadata& smeta); + + virtual void TraversalFeaturesImpl( + const SentenceMetadata& smeta, const HG::Edge& edge, + const std::vector<const void*>& ant_contexts, + SparseVector<double>* features, SparseVector<double>* estimated_features, + void* out_context) const; + + private: + SoftSynFeatureImpl* pimpl_; +}; + +struct SoftSynFeatureFactory : public FactoryBase<FeatureFunction> { + FP Create(std::string param) const; + std::string usage(bool params, bool verbose) const; +}; + +#endif /* FF_SOFT_SYN_H_ */ |