{"action":"created","comment":{"url":"https://api.github.com/repos/kaldi-asr/kaldi/pulls/comments/41704969","id":41704969,"diff_hunk":"@@ -468,99 +469,221 @@ template<class Arc> class DeterminizerStar {\n   // Called by ProcessSubset.\n   // Has no side effects except on the repository.\n \n+  struct EpsilonClosureInfo {\n+    EpsilonClosureInfo() {}\n+\n+    EpsilonClosureInfo(Element e, Weight w, bool i, int d = 0) :\n+      element(e), weight_to_process(w), in_queue(i), depth(d) {}\n+\n+    // the weight in the Element struct is the total current weight\n+    // that has been processed already\n+    Element element;\n+\n+    // this stores the weight that we haven't processed (propagated)\n+    Weight weight_to_process;\n+\n+    // whether \"this\" struct is in the queue\n+    // we store the info here so that we don't have to look it up every time\n+    bool in_queue;\n+\n+    // depth is the max number of epsilons (so far) from the original element set\n+    // e.g. if the original set is (s1, s2)\n+    // s1 -eps-> s4\n+    // s2 -eps-> s3 -eps-> s4\n+    // then the depth for s4 would eventually be 2\n+\n+    // to avoid duplicate of computation, we use a priority_queue for storing\n+    // the state_id's to process, and always pick the one with the smallest\n+    // depth so far first\n+    //\n+    // this would be similar to topo-sort the states before processing;\n+    // (not quite identical since we don't compute the definitive depth first,\n+    // but gradually update the depth while running\n+    // it seems to speed up the process very significantly already\n+    int depth;\n+  };\n+\n+  // this is the struct that is put into the priority_queue. \n+  // The comparison operator makes sure that the queue.top() returns\n+  // the one with the least depth\n+  struct IdAndDepth {\n+    IdAndDepth (InputStateId i, int d):\n+      id(i), depth(d) {}\n+    InputStateId id;\n+    int depth;\n+    bool operator <(const IdAndDepth& other) const {\n+      return this->depth > other.depth;  // we want the lowest depth on top\n+    }\n+  };\n+  \n+  // queue for EpsilonClosure() function\n+  // put it here so the memeory allocation for better effiency\n+  // otherwise it gets created and destroyed constantly, also\n+  // possibly a lot of resize() call the for underlying vector\n+  priority_queue<IdAndDepth> queue;\n+\n+  // Sub-routine that we call in EpsilonClosure()\n+  // To avoid the function getting too long, we make it a separate function\n+  // It takes the current \"unprocessed_weight\" and propagate it to the \n+  // states accessible from elem.state by an epsilon arc\n+  // and add the results to cur_subset.\n+  void ExpandOneElement(const Element &elem,\n+                        bool sorted,\n+                        Weight unprocessed_weight,\n+                        std::map<InputStateId, EpsilonClosureInfo> *cur_subset,\n+                        int this_depth) {\n+    // now we are going to propagate the \"unprocessed_weight\"\n+    for (ArcIterator<Fst<Arc> > aiter(*ifst_, elem.state);\n+         !aiter.Done(); aiter.Next()) {\n+      const Arc &arc = aiter.Value();\n+      if (sorted && arc.ilabel > 0) {\n+        break;\n+        // Break from the loop: due to sorting there will be no\n+        // more transitions with epsilons as input labels.\n+      }\n+      if (arc.ilabel == 0) {  // Epsilon transition.\n+        Element next_elem;\n+        next_elem.state = arc.nextstate;\n+        next_elem.weight = Weight::Zero();\n+        Weight next_unprocessed_weight\n+                       = Times(unprocessed_weight, arc.weight);\n+\n+        // now must append strings\n+        if (arc.olabel == 0)\n+          next_elem.string = elem.string;\n+        else {\n+          vector<Label> seq;\n+          repository_.SeqOfId(elem.string, &seq);\n+          if (arc.olabel != 0)\n+            seq.push_back(arc.olabel);\n+          next_elem.string = repository_.IdOfSeq(seq);\n+        }","path":"src/fstext/determinize-star-inl.h","position":100,"original_position":100,"commit_id":"5ed40029823b2b65c4e2f385bc5634240e3c460b","original_commit_id":"5ed40029823b2b65c4e2f385bc5634240e3c460b","user":{"login":"danpovey","id":3298747,"avatar_url":"https://avatars.githubusercontent.com/u/3298747?v=3","gravatar_id":"","url":"https://api.github.com/users/danpovey","html_url":"https://github.com/danpovey","followers_url":"https://api.github.com/users/danpovey/followers","following_url":"https://api.github.com/users/danpovey/following{/other_user}","gists_url":"https://api.github.com/users/danpovey/gists{/gist_id}","starred_url":"https://api.github.com/users/danpovey/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/danpovey/subscriptions","organizations_url":"https://api.github.com/users/danpovey/orgs","repos_url":"https://api.github.com/users/danpovey/repos","events_url":"https://api.github.com/users/danpovey/events{/privacy}","received_events_url":"https://api.github.com/users/danpovey/received_events","type":"User","site_admin":false},"body":"Hainan - about the problem we were trying to solve with the 'in_queue' variable... I think I may have a way to solve this.\r\nIf you take the rest of this function starting from this line (and this function is anyway too long), and make it a function, e.g. AddOneElement(const Element &element, int32 depth);\r\nthen you could call that same function when iterating over input_subset [i.e. AddOneElement(input_subset[i], 0)].\r\nAlthough this would have an O(n log n) lookup, you already have such a thing when creating the initial map, so there is no loss-- this way avoid having to have two such lookups.","created_at":"2015-10-11T04:05:59Z","updated_at":"2015-10-11T04:05:59Z","html_url":"https://github.com/kaldi-asr/kaldi/pull/208#discussion_r41704969","pull_request_url":"https://api.github.com/repos/kaldi-asr/kaldi/pulls/208","_links":{"self":{"href":"https://api.github.com/repos/kaldi-asr/kaldi/pulls/comments/41704969"},"html":{"href":"https://github.com/kaldi-asr/kaldi/pull/208#discussion_r41704969"},"pull_request":{"href":"https://api.github.com/repos/kaldi-asr/kaldi/pulls/208"}}},"pull_request":{"url":"https://api.github.com/repos/kaldi-asr/kaldi/pulls/208","id":46830812,"html_url":"https://github.com/kaldi-asr/kaldi/pull/208","diff_url":"https://github.com/kaldi-asr/kaldi/pull/208.diff","patch_url":"https://github.com/kaldi-asr/kaldi/pull/208.patch","issue_url":"https://api.github.com/repos/kaldi-asr/kaldi/issues/208","number":208,"state":"open","locked":false,"title":"fixed the bug where fstdeterminizestar sometimes computes the wrong w…","user":{"login":"hainan-xv","id":5440014,"avatar_url":"https://avatars.githubusercontent.com/u/5440014?v=3","gravatar_id":"","url":"https://api.github.com/users/hainan-xv","html_url":"https://github.com/hainan-xv","followers_url":"https://api.github.com/users/hainan-xv/followers","following_url":"https://api.github.com/users/hainan-xv/following{/other_user}","gists_url":"https://api.github.com/users/hainan-xv/gists{/gist_id}","starred_url":"https://api.github.com/users/hainan-xv/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hainan-xv/subscriptions","organizations_url":"https://api.github.com/users/hainan-xv/orgs","repos_url":"https://api.github.com/users/hainan-xv/repos","events_url":"https://api.github.com/users/hainan-xv/events{/privacy}","received_events_url":"https://api.github.com/users/hainan-xv/received_events","type":"User","site_admin":false},"body":"…eight under log-semiring with lots of epsilons","created_at":"2015-10-05T20:41:40Z","updated_at":"2015-10-11T04:05:59Z","closed_at":null,"merged_at":null,"merge_commit_sha":"4194f8aac83238bc5a8de8ef685022e894ab18f7","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/kaldi-asr/kaldi/pulls/208/commits","review_comments_url":"https://api.github.com/repos/kaldi-asr/kaldi/pulls/208/comments","review_comment_url":"https://api.github.com/repos/kaldi-asr/kaldi/pulls/comments{/number}","comments_url":"https://api.github.com/repos/kaldi-asr/kaldi/issues/208/comments","statuses_url":"https://api.github.com/repos/kaldi-asr/kaldi/statuses/5ed40029823b2b65c4e2f385bc5634240e3c460b","head":{"label":"hainan-xv:fstdeterminizestar","ref":"fstdeterminizestar","sha":"5ed40029823b2b65c4e2f385bc5634240e3c460b","user":{"login":"hainan-xv","id":5440014,"avatar_url":"https://avatars.githubusercontent.com/u/5440014?v=3","gravatar_id":"","url":"https://api.github.com/users/hainan-xv","html_url":"https://github.com/hainan-xv","followers_url":"https://api.github.com/users/hainan-xv/followers","following_url":"https://api.github.com/users/hainan-xv/following{/other_user}","gists_url":"https://api.github.com/users/hainan-xv/gists{/gist_id}","starred_url":"https://api.github.com/users/hainan-xv/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hainan-xv/subscriptions","organizations_url":"https://api.github.com/users/hainan-xv/orgs","repos_url":"https://api.github.com/users/hainan-xv/repos","events_url":"https://api.github.com/users/hainan-xv/events{/privacy}","received_events_url":"https://api.github.com/users/hainan-xv/received_events","type":"User","site_admin":false},"repo":{"id":43703911,"name":"kaldi","full_name":"hainan-xv/kaldi","owner":{"login":"hainan-xv","id":5440014,"avatar_url":"https://avatars.githubusercontent.com/u/5440014?v=3","gravatar_id":"","url":"https://api.github.com/users/hainan-xv","html_url":"https://github.com/hainan-xv","followers_url":"https://api.github.com/users/hainan-xv/followers","following_url":"https://api.github.com/users/hainan-xv/following{/other_user}","gists_url":"https://api.github.com/users/hainan-xv/gists{/gist_id}","starred_url":"https://api.github.com/users/hainan-xv/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hainan-xv/subscriptions","organizations_url":"https://api.github.com/users/hainan-xv/orgs","repos_url":"https://api.github.com/users/hainan-xv/repos","events_url":"https://api.github.com/users/hainan-xv/events{/privacy}","received_events_url":"https://api.github.com/users/hainan-xv/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/hainan-xv/kaldi","description":"This is now the official location of the Kaldi project.","fork":true,"url":"https://api.github.com/repos/hainan-xv/kaldi","forks_url":"https://api.github.com/repos/hainan-xv/kaldi/forks","keys_url":"https://api.github.com/repos/hainan-xv/kaldi/keys{/key_id}","collaborators_url":"https://api.github.com/repos/hainan-xv/kaldi/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/hainan-xv/kaldi/teams","hooks_url":"https://api.github.com/repos/hainan-xv/kaldi/hooks","issue_events_url":"https://api.github.com/repos/hainan-xv/kaldi/issues/events{/number}","events_url":"https://api.github.com/repos/hainan-xv/kaldi/events","assignees_url":"https://api.github.com/repos/hainan-xv/kaldi/assignees{/user}","branches_url":"https://api.github.com/repos/hainan-xv/kaldi/branches{/branch}","tags_url":"https://api.github.com/repos/hainan-xv/kaldi/tags","blobs_url":"https://api.github.com/repos/hainan-xv/kaldi/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/hainan-xv/kaldi/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/hainan-xv/kaldi/git/refs{/sha}","trees_url":"https://api.github.com/repos/hainan-xv/kaldi/git/trees{/sha}","statuses_url":"https://api.github.com/repos/hainan-xv/kaldi/statuses/{sha}","languages_url":"https://api.github.com/repos/hainan-xv/kaldi/languages","stargazers_url":"https://api.github.com/repos/hainan-xv/kaldi/stargazers","contributors_url":"https://api.github.com/repos/hainan-xv/kaldi/contributors","subscribers_url":"https://api.github.com/repos/hainan-xv/kaldi/subscribers","subscription_url":"https://api.github.com/repos/hainan-xv/kaldi/subscription","commits_url":"https://api.github.com/repos/hainan-xv/kaldi/commits{/sha}","git_commits_url":"https://api.github.com/repos/hainan-xv/kaldi/git/commits{/sha}","comments_url":"https://api.github.com/repos/hainan-xv/kaldi/comments{/number}","issue_comment_url":"https://api.github.com/repos/hainan-xv/kaldi/issues/comments{/number}","contents_url":"https://api.github.com/repos/hainan-xv/kaldi/contents/{+path}","compare_url":"https://api.github.com/repos/hainan-xv/kaldi/compare/{base}...{head}","merges_url":"https://api.github.com/repos/hainan-xv/kaldi/merges","archive_url":"https://api.github.com/repos/hainan-xv/kaldi/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/hainan-xv/kaldi/downloads","issues_url":"https://api.github.com/repos/hainan-xv/kaldi/issues{/number}","pulls_url":"https://api.github.com/repos/hainan-xv/kaldi/pulls{/number}","milestones_url":"https://api.github.com/repos/hainan-xv/kaldi/milestones{/number}","notifications_url":"https://api.github.com/repos/hainan-xv/kaldi/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/hainan-xv/kaldi/labels{/name}","releases_url":"https://api.github.com/repos/hainan-xv/kaldi/releases{/id}","created_at":"2015-10-05T18:10:23Z","updated_at":"2015-10-05T18:10:36Z","pushed_at":"2015-10-11T03:36:43Z","git_url":"git://github.com/hainan-xv/kaldi.git","ssh_url":"git@github.com:hainan-xv/kaldi.git","clone_url":"https://github.com/hainan-xv/kaldi.git","svn_url":"https://github.com/hainan-xv/kaldi","homepage":"http://kaldi-asr.org","size":72943,"stargazers_count":0,"watchers_count":0,"language":"C++","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"kaldi-asr:master","ref":"master","sha":"4d009fec3d6d4e47e0e929d0f3a30cdce07872f2","user":{"login":"kaldi-asr","id":11650082,"avatar_url":"https://avatars.githubusercontent.com/u/11650082?v=3","gravatar_id":"","url":"https://api.github.com/users/kaldi-asr","html_url":"https://github.com/kaldi-asr","followers_url":"https://api.github.com/users/kaldi-asr/followers","following_url":"https://api.github.com/users/kaldi-asr/following{/other_user}","gists_url":"https://api.github.com/users/kaldi-asr/gists{/gist_id}","starred_url":"https://api.github.com/users/kaldi-asr/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kaldi-asr/subscriptions","organizations_url":"https://api.github.com/users/kaldi-asr/orgs","repos_url":"https://api.github.com/users/kaldi-asr/repos","events_url":"https://api.github.com/users/kaldi-asr/events{/privacy}","received_events_url":"https://api.github.com/users/kaldi-asr/received_events","type":"Organization","site_admin":false},"repo":{"id":34275045,"name":"kaldi","full_name":"kaldi-asr/kaldi","owner":{"login":"kaldi-asr","id":11650082,"avatar_url":"https://avatars.githubusercontent.com/u/11650082?v=3","gravatar_id":"","url":"https://api.github.com/users/kaldi-asr","html_url":"https://github.com/kaldi-asr","followers_url":"https://api.github.com/users/kaldi-asr/followers","following_url":"https://api.github.com/users/kaldi-asr/following{/other_user}","gists_url":"https://api.github.com/users/kaldi-asr/gists{/gist_id}","starred_url":"https://api.github.com/users/kaldi-asr/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kaldi-asr/subscriptions","organizations_url":"https://api.github.com/users/kaldi-asr/orgs","repos_url":"https://api.github.com/users/kaldi-asr/repos","events_url":"https://api.github.com/users/kaldi-asr/events{/privacy}","received_events_url":"https://api.github.com/users/kaldi-asr/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/kaldi-asr/kaldi","description":"This is now the official location of the Kaldi project.","fork":false,"url":"https://api.github.com/repos/kaldi-asr/kaldi","forks_url":"https://api.github.com/repos/kaldi-asr/kaldi/forks","keys_url":"https://api.github.com/repos/kaldi-asr/kaldi/keys{/key_id}","collaborators_url":"https://api.github.com/repos/kaldi-asr/kaldi/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/kaldi-asr/kaldi/teams","hooks_url":"https://api.github.com/repos/kaldi-asr/kaldi/hooks","issue_events_url":"https://api.github.com/repos/kaldi-asr/kaldi/issues/events{/number}","events_url":"https://api.github.com/repos/kaldi-asr/kaldi/events","assignees_url":"https://api.github.com/repos/kaldi-asr/kaldi/assignees{/user}","branches_url":"https://api.github.com/repos/kaldi-asr/kaldi/branches{/branch}","tags_url":"https://api.github.com/repos/kaldi-asr/kaldi/tags","blobs_url":"https://api.github.com/repos/kaldi-asr/kaldi/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/kaldi-asr/kaldi/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/kaldi-asr/kaldi/git/refs{/sha}","trees_url":"https://api.github.com/repos/kaldi-asr/kaldi/git/trees{/sha}","statuses_url":"https://api.github.com/repos/kaldi-asr/kaldi/statuses/{sha}","languages_url":"https://api.github.com/repos/kaldi-asr/kaldi/languages","stargazers_url":"https://api.github.com/repos/kaldi-asr/kaldi/stargazers","contributors_url":"https://api.github.com/repos/kaldi-asr/kaldi/contributors","subscribers_url":"https://api.github.com/repos/kaldi-asr/kaldi/subscribers","subscription_url":"https://api.github.com/repos/kaldi-asr/kaldi/subscription","commits_url":"https://api.github.com/repos/kaldi-asr/kaldi/commits{/sha}","git_commits_url":"https://api.github.com/repos/kaldi-asr/kaldi/git/commits{/sha}","comments_url":"https://api.github.com/repos/kaldi-asr/kaldi/comments{/number}","issue_comment_url":"https://api.github.com/repos/kaldi-asr/kaldi/issues/comments{/number}","contents_url":"https://api.github.com/repos/kaldi-asr/kaldi/contents/{+path}","compare_url":"https://api.github.com/repos/kaldi-asr/kaldi/compare/{base}...{head}","merges_url":"https://api.github.com/repos/kaldi-asr/kaldi/merges","archive_url":"https://api.github.com/repos/kaldi-asr/kaldi/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/kaldi-asr/kaldi/downloads","issues_url":"https://api.github.com/repos/kaldi-asr/kaldi/issues{/number}","pulls_url":"https://api.github.com/repos/kaldi-asr/kaldi/pulls{/number}","milestones_url":"https://api.github.com/repos/kaldi-asr/kaldi/milestones{/number}","notifications_url":"https://api.github.com/repos/kaldi-asr/kaldi/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/kaldi-asr/kaldi/labels{/name}","releases_url":"https://api.github.com/repos/kaldi-asr/kaldi/releases{/id}","created_at":"2015-04-20T17:23:16Z","updated_at":"2015-10-10T11:16:18Z","pushed_at":"2015-10-11T03:36:44Z","git_url":"git://github.com/kaldi-asr/kaldi.git","ssh_url":"git@github.com:kaldi-asr/kaldi.git","clone_url":"https://github.com/kaldi-asr/kaldi.git","svn_url":"https://github.com/kaldi-asr/kaldi","homepage":"http://kaldi-asr.org","size":76189,"stargazers_count":228,"watchers_count":228,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":131,"mirror_url":null,"open_issues_count":18,"forks":131,"open_issues":18,"watchers":228,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/kaldi-asr/kaldi/pulls/208"},"html":{"href":"https://github.com/kaldi-asr/kaldi/pull/208"},"issue":{"href":"https://api.github.com/repos/kaldi-asr/kaldi/issues/208"},"comments":{"href":"https://api.github.com/repos/kaldi-asr/kaldi/issues/208/comments"},"review_comments":{"href":"https://api.github.com/repos/kaldi-asr/kaldi/pulls/208/comments"},"review_comment":{"href":"https://api.github.com/repos/kaldi-asr/kaldi/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/kaldi-asr/kaldi/pulls/208/commits"},"statuses":{"href":"https://api.github.com/repos/kaldi-asr/kaldi/statuses/5ed40029823b2b65c4e2f385bc5634240e3c460b"}}}}