You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@iotdb.apache.org by GitBox <gi...@apache.org> on 2022/09/12 06:54:09 UTC
[GitHub] [iotdb] Cpaulyz opened a new pull request, #7289: [IOTDB-4356] De-duplication of PathPatternTree
Cpaulyz opened a new pull request, #7289:
URL: https://github.com/apache/iotdb/pull/7289
## Description
Fix the bug related to duplicate paths in `PathPatternTree`
1. When `appendPathPattern`, `PathPatternTree` should judge the inclusion relationship between new path and existed paths. The included path should not be stored. The added Pattern may not be a fullPath, so `PathPatternTree` used `matchFullPath()` incorrectly. This pr implements an algorithm to judge the partialPath inclusion relationship to replace `matchFullPath()`.
3. When `getAllDevicePatterns`, `PathPatternTree` should de-duplicate the result set.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@iotdb.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [iotdb] MarcosZyk merged pull request #7289: [IOTDB-4356] De-duplication of PathPatternTree
Posted by GitBox <gi...@apache.org>.
MarcosZyk merged PR #7289:
URL: https://github.com/apache/iotdb/pull/7289
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@iotdb.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [iotdb] MarcosZyk commented on a diff in pull request #7289: [IOTDB-4356] De-duplication of PathPatternTree
Posted by GitBox <gi...@apache.org>.
MarcosZyk commented on code in PR #7289:
URL: https://github.com/apache/iotdb/pull/7289#discussion_r969074170
##########
node-commons/src/main/java/org/apache/iotdb/commons/path/PartialPath.java:
##########
@@ -355,6 +355,57 @@ public boolean prefixMatchFullPath(PartialPath rPath) {
return true;
}
+ /**
+ * Test if this path pattern includes input path pattern. e.g. "root.**" includes "root.sg.**",
+ * "root.*.d.s" includes "root.sg.d.s", "root.sg.**" does not include "root.**.s", "root.*.d.s"
+ * does not include "root.sg.d1.*"
+ *
+ * @param rPath a pattern path of a timeseries
+ * @return true if this path pattern includes input path pattern, otherwise return false
+ */
+ public boolean include(PartialPath rPath) {
+ String[] rNodes = rPath.getNodes();
+ String[] lNodes = nodes.clone();
+ // Replace * with ** if they are adjacent to each other
+ for (int i = 1; i < lNodes.length; i++) {
+ if (MULTI_LEVEL_PATH_WILDCARD.equals(lNodes[i - 1])
+ && ONE_LEVEL_PATH_WILDCARD.equals(lNodes[i])) {
+ lNodes[i] = MULTI_LEVEL_PATH_WILDCARD;
+ }
+ if (MULTI_LEVEL_PATH_WILDCARD.equals(lNodes[lNodes.length - i])
+ && ONE_LEVEL_PATH_WILDCARD.equals(lNodes[lNodes.length - 1 - i])) {
+ lNodes[lNodes.length - 1 - i] = MULTI_LEVEL_PATH_WILDCARD;
+ }
+ }
+ // dp[i][j] means if nodes1[0:i) includes nodes[0:j)
+ boolean[] dp = new boolean[rNodes.length + 1];
+ dp[0] = true;
+ for (int i = 1; i <= lNodes.length; i++) {
+ boolean[] newDp = new boolean[rNodes.length + 1];
+ for (int j = i; j <= rNodes.length; j++) {
+ if (lNodes[i - 1].equals(MULTI_LEVEL_PATH_WILDCARD)) {
+ // if encounter MULTI_LEVEL_PATH_WILDCARD
+ if (dp[j - 1]) {
+ for (int k = j; k <= rNodes.length; k++) {
+ newDp[k] = true;
+ }
+ break;
+ }
+ } else {
+ // if without MULTI_LEVEL_PATH_WILDCARD, scan and check
+ if (!rNodes[j - 1].equals(MULTI_LEVEL_PATH_WILDCARD)
+ && (lNodes[i - 1].equals(ONE_LEVEL_PATH_WILDCARD)
+ || lNodes[i - 1].equals(rNodes[j - 1]))) {
+ // if nodes1[i-1] includes rNodes[j-1], dp[i][j] = dp[i-1][j-1]
+ newDp[j] |= dp[j - 1];
+ }
+ }
+ }
+ dp = newDp;
+ }
+ return dp[rNodes.length];
Review Comment:
Maybe add an dp table example as comments will help understand much better.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@iotdb.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org